【BZOJ】【2756】【SCOI2012】奇怪的游戏

2023-01-27 21:18:14

网络流-最大流

　　这题……建模部分先略过

　　这道题是会卡时限的T_T俺的Dinic被卡了，在此放几篇很棒的讲网络流算法的文章，至于大家耳熟能详的论文就不放了……

　　http://www.cppblog.com/panzhizhou/articles/172978.html?opt=admin

　　里面的各种超链接也很不错的……

　　好的来重新更新一下……这题因为要二分，需要多次重建跑最大流，所以不能用像lrj大爷的白书上那样用vector存边（太慢），需用前向星= =

　　然后……本蒻由于第一次写前向星，且印象中好像不加【当前弧优化】效率也不会低太多……所以顺利TLE了。事实上当前弧的设计还是和vector存边时差不多的，而且很有必要优化这一下……

round #1 2b版：

 /**************************************************************

     Problem: 2756

     User: ProgrammingApe

     Language: C++

     Result: Accepted

     Time:8000 ms

     Memory:2008 kb

 ****************************************************************/

 //BZOJ 2756

 #include<queue>

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 const int N=,INF=~0u>>;

 const long long infll=~0uLL>>;

 const int fx[]={,,-,},

           fy[]={,,,-};

 typedef long long LL;

 //#define debug

 void read(int &v){

     v=; int sig=;

     char ch=getchar();

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

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

     v*=sig;

 }

 int n,m,a[N][N],d[N*N],cur[N*N],s,t,cnt;

 bool color[N][N];

 LL sum[];

 struct edge{

     int from,to;

     LL cap,flow;

     int next;

 }E[N*N*];

 int head[];

 //vector<edge>E;

 //vector<int>G[2000];

 void add(int from,int to,LL cap){

     E[++cnt]=(edge){from,to,cap,,head[from]};

     head[from]=cnt;

     E[++cnt]=(edge){to,from,,,head[to]};

     head[to]=cnt;

 }

 //queue<int>Q;//·ÅÔÚmklevelÀïÃæ»áÂýÐí¶à

 int Q[N*N];

 bool mklevel(){

     memset(d,,sizeof d);

     int l=,r=;

     d[s]=; Q[r++]=s;

     while(l<r){

         int x=Q[l++];

         for(int i=head[x];i;i=E[i].next){

             edge&e=E[i];

             if (d[e.to]> && e.cap>e.flow){

                 d[e.to]=d[x]+;

                 Q[r++]=e.to;

             }

         }

     }

     return d[t]<;

 }

 LL dfs(int x,LL a){

     if (x==t||a==) return a;

     LL flow=;

     for(int &i=cur[x];i;i=E[i].next){

         edge&e=E[i];

         if (d[e.to]!=d[x]+) continue;

         LL f=dfs(e.to,min(a,e.cap-e.flow));

         if (f>){

             flow+=f;

             e.flow+=f;

             E[((i-)^)+].flow-=f;

             a-=f;

             if (a==) break;

         }

     }

     return flow;

 }

 LL dinic(){

     LL flow=;

     while(mklevel()){

         F(i,s,t) cur[i]=head[i];//µ±Ç°»¡ÓÅ»¯ºÜÖØÒªµÄT_T

         flow+=dfs(s,infll);//ÕâÀïÒ²Òª¸Ä³Éinfll

     }

     return flow;

 }

 LL Total=;

 int maxw=;

 void solve1(){

     memset(E,,sizeof E);

     memset(head,,sizeof head); cnt=;

     LL d=sum[]-sum[];

     if (d<maxw) {printf("-1\n"); return;}

     int x,y;

     Total=;

     F(i,,n)

         F(j,,m){

 //          if (a[i][j]>d) {printf("-1\n"); return;}

             if (color[i][j]) add((i-)*m+j,t,d-a[i][j]);

             else{

                 add(s,(i-)*m+j,d-a[i][j]);

                 F(k,,){

                     x=i+fx[k],y=j+fy[k];

                     if (x<||y<||x>n||y>m) continue;

                     add( (i-)*m+j , (x-)*m+y , infll);

                 }

                 Total+=d-a[i][j];

             }

         }

     LL ans=dinic();

     if (Total==ans) printf("%lld\n",ans);

     else printf("-1\n");

 }

 bool check(LL x){

     memset(E,,sizeof E);

     memset(head,,sizeof head);

     cnt=;//Çå¿Õ±ß¼¯Êý×éµÄÊ±ºò£¬¼ÇµÃ°Ñ±ß¼¯´óÐ¡cntÒ²Çå¿Õ

     Total=;

     F(i,,n)

         F(j,,m){

             if (color[i][j]) add( (i-)*m+j,t,x-a[i][j] );

             else{

                 add(s,(i-)*m+j,x-a[i][j]);

                 F(k,,){

                     int tx=i+fx[k],ty=j+fy[k];

                     if (tx<||ty<||tx>n||ty>m) continue;

                     add( (i-)*m+j , (tx-)*m+ty , infll);

                 }

                 Total+=x-a[i][j];

             }

         }

     LL flow=dinic();

     return Total==flow;

 }

 void solve(){//Èç¹ûÊÇÅ¼Êý£º¶þ·Ö

     if (sum[]!=sum[]){

         printf("-1\n");

         return;

     }

     LL l=maxw,r=l*,mid,ans=-;//¾ÓÈ»ÊÇÕâÀïÍüÁË¸Ä¡

     while(l<r){

 //      cout <<l<<" "<<r<<endl;

 //      printf("l=%lld r=%lld\n",l,r);

         mid=l+r>>;

         if (check(mid)) {ans=Total; r=mid;}

         else l=mid+;

     }

     if (ans!=-) printf("%lld\n",ans);

     else printf("-1\n");

 }

 int main(){

     #ifndef ONLINE_JUDGE

     freopen("input.txt","r",stdin);

 //  freopen("output.txt","w",stdout);

     #endif

     int T;

     scanf("%d",&T);

     while(T--){

         read(n),read(m);

         s=; t=n*m+;

         memset(a,,sizeof a);

         memset(color,,sizeof color);

         sum[]=sum[]=maxw=;

         F(i,,n) F(j,,m) {

             read(a[i][j]);

             color[i][j]=(i+j)&;

             sum[color[i][j]]+=a[i][j];

             maxw=max(maxw,a[i][j]);

         }

         if ((n&) && (m&)) solve1();

         else solve();

     }

     return ;

 }

round #2 修改（缩短）版：

 /**************************************************************

     Problem: 2756

     User: Tunix

     Language: C++

     Result: Accepted

     Time:7912 ms

     Memory:1552 kb

 ****************************************************************/

 //BZOJ 2756

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 typedef long long LL;

 //#define debug

 const int N=;

 const long long infll=~0uLL>>;

 const int fx[]={,,-,},

           fy[]={,,,-};

 void read(int &v){

     int sign=; v=;

     char ch=getchar();

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

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

     v*=sign;

 }

 /*********************网络流**********************/

 int n,m,val[N][N],color[N][N],cnt=,s,t;

 int head[N*N],cur[N*N];

 LL sum[];

 struct edge{

     int from,to;

     LL cap,flow;

     int next;

 }E[N*N*];

 void add(int from,int to,LL cap){

     E[++cnt]=(edge){from,to,cap,,head[from]};

     head[from]=cnt;

     E[++cnt]=(edge){to,from,,,head[to]};

     head[to]=cnt;

 }

 int d[N*N],Q[N*N];

 bool mklevel(){

     memset(d,,sizeof d);

     d[s]=; int l=,r=;

     Q[r++]=s;

     while(l<r){

         int x=Q[l++];

         for(int i=head[x];i;i=E[i].next){

             edge &e=E[i];

             if (d[e.to]> && e.cap>e.flow){

                 d[e.to]=d[x]+;

                 Q[r++]=e.to;

             }

         }

     }

     return d[t]<;

 }

 LL dfs(int x,LL a){

     if (x==t || a==) return a;

     LL flow=,f;

     for(int &i=cur[x];i;i=E[i].next){

         edge &e=E[i];

         if (d[e.to]!=d[x]+) continue;

         f=dfs(e.to,min(a,e.cap-e.flow));

         if (f>){

             e.flow+=f;

             flow+=f;

             a-=f;

             E[((i-)^)+].flow-=f;

             if (a==) break;

         }

     }

     return flow;

 }

 LL dinic(){

     LL flow=;

     while(mklevel()) {

         F(i,s,t) cur[i]=head[i];

         flow+=dfs(s,infll);

     }

     return flow;

 }

 /*************************************************/

 inline int get(int x,int y){ return (x-)*m+y; }

 LL total;

 inline bool check(LL D){

     memset(E,,sizeof E);

     memset(head,,sizeof head);

     cnt=; total=;

     F(i,,n)

         F(j,,m){

             if (color[i][j]) add( get(i,j),t,D-val[i][j] );

             else{

                 add( s,get(i,j),D-val[i][j] );

                 F(k,,){

                     int tx=i+fx[k],ty=j+fy[k];

                     if (tx<||ty<||tx>n||ty>m) continue;

                     add( get(i,j),get(tx,ty),infll );

                 }

                 total+=D-val[i][j];

             }

         }

     LL flow=dinic();

     return total==flow;

 }

 int maxw;

 void work(){

     s=; t=n*m+;

     if ((n&) && (m&)){

         LL D=sum[]-sum[];

         if (D<maxw) printf("-1\n");

         else{

             if(check(D)) printf("%lld\n",total);

             else printf("-1\n");

         }

     }

     else {

         if (sum[]!=sum[]){

             printf("-1\n");

             return;

         }

         LL l=maxw,r=l*,mid,ans=-;

         while(l<r){

 //          printf("l=%lld r=%lld\n",l,r);

             mid=l+r>>;

             if (check(mid)) {r=mid; ans=total;}

             else l=mid+;

         }

         if (ans==-) printf("-1\n");

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

     }

 }

 int main(){

     #ifndef ONLINE_JUDGE

     freopen("input.txt","r",stdin);

     #endif

     int T; read(T);

     while(T--){

         memset(val,,sizeof val);

         memset(color,,sizeof color);

         sum[]=sum[]=;

         maxw=;

         read(n); read(m);

         F(i,,n)

             F(j,,m){

                 read(val[i][j]);

                 color[i][j]=(i+j)&;

                 sum[color[i][j]]+=val[i][j];

                 if (val[i][j]>maxw) maxw=val[i][j];

             }

         work();

     }

     return ;

 }

2756: [SCOI2012]奇怪的游戏

Time Limit: 40 Sec Memory Limit: 128 MB
Submit: 1936 Solved: 508
[Submit][Status][Discuss]

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

Source

[Submit][Status][Discuss]

码农公寓