洛谷P3057 [USACO12NOV]远处的牧场Distant Pastures

因为是稀疏图（一个点最多连接4条边)

所以每个点跑SPFA就行了

 

1 #include 
     
        2 #define LL long long  3 #define For(i,j,k) for(int i=j;i<=k;i++)  4 #define Dow(i,j,k) for(int i=j;i>=k;i--)  5 using namespace std ;  6  7 const int N = 911 ;  8 const LL inf = 1e15 ;  9 const int dx[]={
   0,1,0,0,-1} ; 10 const int dy[]={
   0,0,1,-1,0} ; 11 int n,cnt,h,t,A,B ; 12 char s[33][33] ; 13 struct node{14     int to,pre,val ; 15 }e[N*4];16 int q[200011],head[N] ; 17 LL dist[N],Mx ; 18 bool visit[N] ; 19 20 inline int read() 21 {22     int x = 0 , f = 1 ; 23     char ch = getchar() ; 24     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 25     while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; } 26     return x * f ;  27 }28 29 inline void add(int x,int y,int val)30 {31     e[++cnt].to = y ; 32     e[cnt].val = val ; 33     e[cnt].pre = head[x] ; 34     head[x] = cnt ; 35 }36 37 inline void SPFA(int s) 38 {39     For(i,0,n) dist[i] = inf ; 40     For(i,0,n) visit[i] = 0 ; 41     h = 0 ; t = 0 ; 42     q[++t] = s ; dist[s] = 0 ; 43     while(h
      
       Mx) Mx = dist[i] ; 59 }60 61 int main() 62 {63      n = read() ; A = read() ; B = read() ; 64      For(i,1,n) scanf("%s",s[i]+1) ; 65     For(i,1,n) 66       For(j,1,n)67         For(k,1,4) {68             int xx=i+dx[k] ,yy=j+dy[k],val ; 69             if(xx<1||xx>n||yy<1||yy>n) continue ; 70             if(s[i][j]==s[xx][yy]) val = A ; 71             else val=B ; 72             add((i-1)*n+j,(xx-1)*n+yy,val) ;  73          }74     Mx = -1 ;75     n*=n ;  76     For(i,1,n) SPFA( i ) ; 77     printf("%d\n",Mx) ; 78     return 0 ; 79 }