Bzoj2756 [SCOI2012]奇怪的游戏

2756: [SCOI2012]奇怪的游戏

Time Limit: 40 Sec Memory Limit: 128 MB
Submit: 3220 Solved: 886

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

Sample Output

2
-1

HINT

【数据范围】

对于30%的数据，保证 T<=10，1<=N,M<=8

对于100%的数据，保证 T<=10，1<=N,M<=40，所有数为正整数且小于1000000000

最大流。

对原图进行二分图染色，统计黑白格子的个数和各自的数量和。

每次加值，肯定是黑白格子各+1

设最终数值为D，得到：

　　D*cntW-sumW == D*cntB - sumB

如果格子数为奇数，也就是黑白格子不等，D是唯一的，只需要建立流量网络验证是否可行即可。

如果格子数为偶数：如果sum不等，无解，否则可以二分D，验证是否可行并记录答案。

建图方法：

　　S到白格子连边，容量为D-格子权值

　　白格子到四周黑格子连边，容量为INF

　　黑格子到T连边，容量为D-格子权值

_____________

然后就愉快地WA了一串，调了好久好久。在那么一个瞬间察觉到哪里不对，再一看代码……我的init函数放在了二分前面，处理奇数情况时好像没调用？

23333翻出了第一次提交的记录，代码复制出来，换了init的位置，AC

233333这好像是第三次没有初始化了，第一次是某次写LCA，第二次是网络流

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<queue>
  6 #include<vector>
  7 #define LL long long
  8 using namespace std;
  9 const int mx[5]={0,1,0,-1,0};
 10 const int my[5]={0,0,1,0,-1};
 11 const int mxn=3010;
 12 int read(){
 13     int x=0,f=1;char ch=getchar();
 14     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 15     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 16     return x*f;
 17 }
 18 struct edge{int v,nxt;LL f;}e[mxn<<3];
 19 int hd[mxn],mct=1;
 20 void add_edge(int u,int v,LL f){
 21     e[++mct].v=v;e[mct].f=f;e[mct].nxt=hd[u];hd[u]=mct;return;
 22 }
 23 void ins(int u,int v,LL f){add_edge(u,v,f);add_edge(v,u,0);return;}
 24 int n,m,S,T;
 25 int mp[45][45];
 26 int id[45][45];
 27 int d[mxn];
 28 bool BFS(){
 29     memset(d,0,sizeof d);
 30     queue<int>q;
 31     d[S]=1;
 32     q.push(S);
 33     while(!q.empty()){
 34         int u=q.front();q.pop();
 35         for(int i=hd[u];i;i=e[i].nxt){
 36             int v=e[i].v;
 37             if(!d[v] && e[i].f){
 38                 d[v]=d[u]+1;
 39                 q.push(v);
 40             }
 41         }
 42     }
 43     return d[T];
 44 }
 45 LL DFS(int u,LL lim){
 46     if(u==T)return lim;
 47     LL tmp,f=0;
 48     for(int i=hd[u];i;i=e[i].nxt){
 49         int v=e[i].v;
 50         if(d[v]==d[u]+1 && e[i].f){
 51             tmp=DFS(v,min(lim,e[i].f));
 52             e[i].f-=tmp;
 53             e[i^1].f+=tmp;
 54             lim-=tmp;
 55             f+=tmp;
 56             if(!lim)return f;
 57         }
 58     }
 59     d[u]=0;
 60     return f;
 61 }
 62 LL Dinic(){
 63     LL res=0;
 64     while(BFS())res+=DFS(S,1e16);
 65     return res;
 66 }
 67 void init(){
 68     for(int i=1;i<=n;i++)
 69      for(int j=1;j<=m;j++)
 70         id[i][j]=(i-1)*m+j;
 71     return;
 72 }
 73 LL ans=0;
 74 bool solve(LL lim){
 75     memset(hd,0,sizeof hd);
 76     mct=1;
 77     int i,j;
 78     LL tar=0;
 79     for(i=1;i<=n;i++)
 80      for(j=1;j<=m;j++){
 81         if((i+j)%2==0){
 82             ins(S,id[i][j],lim-mp[i][j]);
 83             tar+=lim-mp[i][j];
 84             for(int k=1;k<=4;k++){
 85                 int nx=i+mx[k];
 86                 int ny=j+my[k];
 87                 if(nx>0 && nx<=n && ny>0 && ny<=m){
 88                     ins(id[i][j],id[nx][ny],1e16);
 89                 }
 90             }
 91         }
 92         else{ins(id[i][j],T,lim-mp[i][j]);}
 93      }
 94     if(Dinic()==tar){
 95         ans=tar;    
 96         return 1;
 97     }
 98     return 0;
 99 }
100 int main()
101 {
102     int Cas=read();
103     int i,j;
104     while(Cas--){
105         int mxnum=-1e9;
106         n=read();m=read();
107         for(i=1;i<=n;i++)
108          for(j=1;j<=m;j++){
109             mp[i][j]=read();
110             mxnum=max(mxnum,mp[i][j]);
111         }
112         S=0;T=n*m+1;
113         init();
114         LL numw=0,numb=0,cntw=0,cntb=0;
115             for(i=1;i<=n;i++)
116                 for(j=1;j<=m;j++){
117                     if((i+j)%2==0){
118                         numw+=mp[i][j];cntw++;
119                     }
120                     else{
121                         numb+=mp[i][j];cntb++;
122                     }
123                 }
124         if(n*m%2==1){
125  
126             LL D=(numw-numb)/(cntw-cntb);
127             if(D>=mxnum && solve(D)){printf("%lld
",ans);}
128             else printf("-1
");
129             continue;
130         }
131         else{
132             if(numb!=numw){
133                 printf("-1
");
134                 continue;
135             }
136             ans=-1;
137             LL l=mxnum,r=1e16;
138             while(l<=r){
139                 LL mid=(l+r)>>1;
140                 if(solve(mid)){
141                     r=mid-1;
142                 }
143                 else l=mid+1;
144             }
145             printf("%lld
",ans);
146         }
147     }
148     return 0;
149 }