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，第二次是网络流

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 #include<vector>

 #define LL long long

 using namespace std;

 const int mx[]={,,,-,};

 const int my[]={,,,,-};

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct edge{int v,nxt;LL f;}e[mxn<<];

 int hd[mxn],mct=;

 void add_edge(int u,int v,LL f){

     e[++mct].v=v;e[mct].f=f;e[mct].nxt=hd[u];hd[u]=mct;return;

 }

 void ins(int u,int v,LL f){add_edge(u,v,f);add_edge(v,u,);return;}

 int n,m,S,T;

 int mp[][];

 int id[][];

 int d[mxn];

 bool BFS(){

     memset(d,,sizeof d);

     queue<int>q;

     d[S]=;

     q.push(S);

     while(!q.empty()){

         int u=q.front();q.pop();

         for(int i=hd[u];i;i=e[i].nxt){

             int v=e[i].v;

             if(!d[v] && e[i].f){

                 d[v]=d[u]+;

                 q.push(v);

             }

         }

     }

     return d[T];

 }

 LL DFS(int u,LL lim){

     if(u==T)return lim;

     LL tmp,f=;

     for(int i=hd[u];i;i=e[i].nxt){

         int v=e[i].v;

         if(d[v]==d[u]+ && e[i].f){

             tmp=DFS(v,min(lim,e[i].f));

             e[i].f-=tmp;

             e[i^].f+=tmp;

             lim-=tmp;

             f+=tmp;

             if(!lim)return f;

         }

     }

     d[u]=;

     return f;

 }

 LL Dinic(){

     LL res=;

     while(BFS())res+=DFS(S,1e16);

     return res;

 }

 void init(){

     for(int i=;i<=n;i++)

      for(int j=;j<=m;j++)

         id[i][j]=(i-)*m+j;

     return;

 }

 LL ans=;

 bool solve(LL lim){

     memset(hd,,sizeof hd);

     mct=;

     int i,j;

     LL tar=;

     for(i=;i<=n;i++)

      for(j=;j<=m;j++){

         if((i+j)%==){

             ins(S,id[i][j],lim-mp[i][j]);

             tar+=lim-mp[i][j];

             for(int k=;k<=;k++){

                 int nx=i+mx[k];

                 int ny=j+my[k];

                 if(nx> && nx<=n && ny> && ny<=m){

                     ins(id[i][j],id[nx][ny],1e16);

                 }

             }

         }

         else{ins(id[i][j],T,lim-mp[i][j]);}

      }

     if(Dinic()==tar){

         ans=tar;

         return ;

     }

     return ;

 }

 int main()

 {

     int Cas=read();

     int i,j;

     while(Cas--){

         int mxnum=-1e9;

         n=read();m=read();

         for(i=;i<=n;i++)

          for(j=;j<=m;j++){

             mp[i][j]=read();

             mxnum=max(mxnum,mp[i][j]);

         }

         S=;T=n*m+;

         init();

         LL numw=,numb=,cntw=,cntb=;

             for(i=;i<=n;i++)

                 for(j=;j<=m;j++){

                     if((i+j)%==){

                         numw+=mp[i][j];cntw++;

                     }

                     else{

                         numb+=mp[i][j];cntb++;

                     }

                 }

         if(n*m%==){

             LL D=(numw-numb)/(cntw-cntb);

             if(D>=mxnum && solve(D)){printf("%lld\n",ans);}

             else printf("-1\n");

             continue;

         }

         else{

             if(numb!=numw){

                 printf("-1\n");

                 continue;

             }

             ans=-;

             LL l=mxnum,r=1e16;

             while(l<=r){

                 LL mid=(l+r)>>;

                 if(solve(mid)){

                     r=mid-;

                 }

                 else l=mid+;

             }

             printf("%lld\n",ans);

         }

     }

     return ;

 }

巴特西