Description
Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N*M 的棋盘上玩，每个格子有一个数。每次 Blinker 会选择两个相邻
的格子，并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同
一个数则输出-1。
Input
输入的第一行是一个整数T，表示输入数据有T轮游戏组成。
每轮游戏的第一行有两个整数N和M， 分别代表棋盘的行数和列数。
接下来有N行，每行 M个数。
Output
对于每个游戏输出最少能使游戏结束的次数，如果永远不能变成同一个数则输出-1。
Sample Input
2
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2
Sample Output
2
-1
-1
HINT
【数据范围】
对于30%的数据，保证 T<=10，1<=N,M<=8
对于100%的数据，保证 T<=10，1<=N,M<=40，所有数为正整数且小于1000000000
题解大家去hzwer里看吧 说的很好 http://hzwer.com/5992.html
这只留一个代码
1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #define MAXN 1010 6 #define LL long long 7 8 using namespace std; 9 10 const LL INF=(1LL<<50); 11 12 struct Quix { 13 int to; 14 int next; 15 LL val; 16 }; 17 Quix e[20010]; 18 19 int head[MAXN<<1],cur[MAXN<<1],tot=1; 20 21 int T,n,m,src,decc,n1,n2,mx=-1; 22 23 LL s1,s2; //血的教训 忘了long long 24 25 int depth[MAXN<<1],a[50][50],color[50][50]; 26 27 int X[4]={0,1,-1,0}; 28 int Y[4]={1,0,0,-1}; //上下左右我竟然少搜了一个方向 29 30 queue<int> Q; 31 32 inline void read(int&x) { 33 int f=1;x=0;char c=getchar(); 34 while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} 35 while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-48;c=getchar();} 36 x=x*f; 37 } 38 39 inline void add(int x,int y,LL z) { 40 e[++tot].to=y; 41 e[tot].val=z; 42 e[tot].next=head[x]; 43 head[x]=tot; 44 } 45 46 inline void add_edge(int x,int y,LL z) { 47 add(x,y,z); 48 add(y,x,0); 49 } 50 51 inline int cal(int i,int j) { 52 return (i-1)*m+j; 53 } 54 55 bool bfs() { 56 for(int i=0;i<=decc;i++) cur[i]=head[i],depth[i]=-1; 57 while(!Q.empty()) Q.pop(); 58 Q.push(src); 59 depth[src]=0; 60 while(!Q.empty()) { 61 int u=Q.front(); 62 Q.pop(); 63 for(int i=head[u];i!=-1;i=e[i].next) { 64 int to=e[i].to; 65 if(e[i].val&&depth[to]==-1) { 66 Q.push(to); 67 depth[to]=depth[u]+1; 68 if(to==decc) return true; 69 } 70 } 71 } 72 return false; 73 } 74 75 LL dfs(int now,LL flow) { 76 if(now==decc) return flow; 77 LL used=0,delat; 78 for(int & i=cur[now];i!=-1;i=e[i].next) { 79 int to=e[i].to; 80 if(e[i].val&&depth[to]==depth[now]+1) { 81 delat=flow-used; 82 delat=dfs(to,min(e[i].val,delat)); 83 e[i].val-=delat; 84 e[i^1].val+=delat; 85 used+=delat; 86 if(used==flow) break; 87 } 88 } 89 if(!used) depth[now]=-1; 90 return used; 91 } 92 93 inline LL dinic() { 94 LL ans=0; 95 while(bfs()) 96 ans+=dfs(src,INF); 97 return ans; 98 } 99 100 inline bool check(LL x) { 101 LL cnt=0; 102 tot=1; 103 memset(head,-1,sizeof head); 104 for(int i=1;i<=n;i++) 105 for(int j=1;j<=m;j++) 106 if(color[i][j]) { 107 add_edge(src,cal(i,j),x-a[i][j]); 108 cnt+=x-a[i][j]; 109 for(int k=0;k<4;k++) { 110 int nx=i+X[k]; 111 int ny=j+Y[k]; 112 if(nx<1||nx>n||ny<1||ny>m) continue; 113 add_edge(cal(i,j),cal(nx,ny),INF); 114 } 115 } 116 else add_edge(cal(i,j),decc,x-a[i][j]); 117 if(dinic()==cnt) return true; 118 return false; 119 } 120 121 inline int hhh() { 122 read(T); 123 while(T--) { 124 mx=-1; 125 n1=n2=s1=s2=0; 126 read(n);read(m); 127 src=0;decc=n*m+1; 128 for(int i=1;i<=n;i++) 129 for(int j=1;j<=m;j++) { 130 read(a[i][j]); 131 color[i][j]=(i+j)&1; 132 mx=max(mx,a[i][j]); 133 if(color[i][j]) s1+=(LL)a[i][j],n1++; 134 else s2+=(LL)a[i][j],n2++; 135 } 136 if(n1!=n2) { 137 LL x=(s2-s1)/(n2-n1); 138 if(x>=mx) 139 if(check(x)) { 140 printf("%lld ",(LL)x*n1-s1); 141 continue; 142 } 143 printf("-1 "); 144 } 145 else { 146 if(s1!=s2) { 147 printf("-1 "); 148 continue; 149 } 150 LL l=mx,r=INF; 151 while(l<=r) { 152 LL mid=(l+r)>>1; 153 if(check(mid)) r=mid-1; 154 else l=mid+1; 155 } 156 printf("%lld ",(LL)l*n1-s1); 157 } 158 } 159 return 0; 160 } 161 162 int sb=hhh(); 163 int main() {;}