首页 > 代码库 > [SCOI2012]奇怪的游戏 (网络流)
[SCOI2012]奇怪的游戏 (网络流)
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=http://www.mamicode.com/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\n",(LL)x*n1-s1);141 continue;142 }143 printf("-1\n");144 }145 else {146 if(s1!=s2) {147 printf("-1\n");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\n",(LL)l*n1-s1);157 }158 } 159 return 0;160 }161 162 int sb=hhh();163 int main() {;}
[SCOI2012]奇怪的游戏 (网络流)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。