[关闭]
@zzzc18 2018-01-21T05:12:29.000000Z 字数 2950 阅读 530

BZOJ2756: [SCOI2012]奇怪的游戏

bzoj 网络流


题就不再念了

Solution

首先对棋盘进行黑白染色,像这样
1.PNG-19.3kB
然后要统计白点个数,初始白点点权和以及黑点个数与初始黑点点权和
显然的是,最终得到的值 可以写作

时直接判断 是否可行,可行则输出解,否则无解
是无意义的,也就是说算不出来
但此时可以看出来,若 可以满足题意 那么 也满足题意(任意的白点都可以有一个与它配对的黑点一起 ,整个图都这么做, 也就可以加出来)
说明了什么?可以二分了
二分 可以求出

二分的 要用到网络流
设源点为 汇点为
到白点连容量为 的边,黑点到 连容量为 的边,相邻的白点和黑点容量为INF
(脑补一下,白点和黑点都要加够 次,白点和黑点之间没有限制)
如果这个图是满流的,说明 可行,否则不可行

这题时限40s,似乎可以用来给不法分子卡评测

注意:long long还是很慢的,memset,memcpy很耗时,刚开始浪数组开太大,卡了一个40s的TLE。。。

  1. #include<queue>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #define LL long long
  6. #define MAXN 100
  7. #define MAXE 10000
  8. #define INF (1LL<<60)
  9. using namespace std;
  10. LL n,m;
  11. LL kase;
  12. LL num[MAXN][MAXN];
  13. LL color[MAXN][MAXN];
  14. struct E{
  15. LL next,to,val;
  16. }edge[MAXE];
  17. LL head[MAXE],edge_num;
  18. LL depth[MAXE],iter[MAXE];
  19. queue<LL> que;
  20. LL s,t;
  21. LL cntw,cntb,sumw,sumb;
  22. LL u[5]={0,1,-1,0,0},v[5]={0,0,0,1,-1};
  23. LL FLOW;
  24. LL MAX;
  25. LL index(LL i,LL j){
  26. return i*m+j;
  27. }
  28. bool inmap(LL x,LL y){
  29. return x<=n && x>=1 && y<=m && y>=1;
  30. }
  31. void addedge(LL x,LL y,LL v){
  32. edge[++edge_num].next=head[x];
  33. edge[edge_num].to=y;
  34. edge[edge_num].val=v;
  35. head[x]=edge_num;
  36. }
  37. void INIT(){
  38. scanf("%lld%lld",&n,&m);
  39. s=m*(n+1)+1,t=m*(n+1)+2;
  40. cntw=cntb=sumw=sumb=0;
  41. LL i,j;
  42. MAX=0;
  43. for(i=1;i<=n;i++){
  44. for(j=1;j<=m;j++){
  45. scanf("%lld",&num[i][j]);
  46. MAX=max(MAX,num[i][j]);
  47. if((j%2)^(i%2))
  48. color[i][j]=1,cntb++,sumb+=num[i][j];
  49. else
  50. color[i][j]=0,cntw++,sumw+=num[i][j];
  51. }
  52. }
  53. }
  54. void Graph(LL x){
  55. LL i,j;
  56. edge_num=1;
  57. memset(head,0,sizeof(head));
  58. FLOW=0;
  59. for(i=1;i<=n;i++){
  60. for(j=1;j<=m;j++){
  61. if(color[i][j]==0){
  62. FLOW+=x-num[i][j];
  63. addedge(s,i*m+j,x-num[i][j]);
  64. addedge(i*m+j,s,0);
  65. LL k;
  66. for(k=1;k<=4;k++){
  67. LL x,y;
  68. x=i+u[k],y=j+v[k];
  69. if(inmap(x,y)){
  70. addedge(index(i,j),index(x,y),INF);
  71. addedge(index(x,y),index(i,j),0);
  72. }
  73. }
  74. }
  75. else{
  76. addedge(i*m+j,t,x-num[i][j]);
  77. addedge(t,i*m+j,0);
  78. }
  79. }
  80. }
  81. }
  82. void BFS(){
  83. memset(depth,-1,sizeof(depth));
  84. que.push(s);
  85. depth[s]=0;
  86. LL i;
  87. while(!que.empty()){
  88. LL fro=que.front();que.pop();
  89. for(i=head[fro];i;i=edge[i].next){
  90. if(edge[i].val>0 && depth[edge[i].to]==-1){
  91. depth[edge[i].to]=depth[fro]+1;
  92. que.push(edge[i].to);
  93. }
  94. }
  95. }
  96. }
  97. LL DFS(LL x,LL f){
  98. if(x==t)
  99. return f;
  100. for(LL &i=iter[x];i;i=edge[i].next){
  101. if(edge[i].val>0 && depth[edge[i].to]==depth[x]+1){
  102. LL tmp=DFS(edge[i].to,min(f,edge[i].val));
  103. if(tmp>0){
  104. edge[i].val-=tmp;
  105. edge[i^1].val+=tmp;
  106. return tmp;
  107. }
  108. }
  109. }
  110. return 0;
  111. }
  112. LL Dinic(){
  113. LL re=0;
  114. while(true){
  115. BFS();
  116. if(depth[t]<0)
  117. break;
  118. LL tmp;
  119. memcpy(iter,head,sizeof(head));
  120. while(true){
  121. tmp=DFS(s,INF);
  122. if(tmp<=0){
  123. break;
  124. }
  125. re+=tmp;
  126. }
  127. }
  128. return re;
  129. }
  130. bool check(LL x){
  131. return FLOW==x;
  132. }
  133. void PLAN1(){
  134. LL x=(sumw-sumb)/(cntw-cntb);
  135. if(x<MAX){
  136. printf("-1\n");
  137. return;
  138. }
  139. Graph(x);
  140. LL tmp=Dinic();
  141. if(check(tmp))
  142. printf("%lld\n",x*cntw-sumw);
  143. else
  144. printf("-1\n");
  145. }
  146. void PLAN2(){
  147. LL l,r;
  148. l=MAX;r=(1LL<<50);
  149. while(l<=r){
  150. LL mid=(l+r)>>1;
  151. Graph(mid);
  152. LL tmp=Dinic();
  153. if(check(tmp))
  154. r=mid-1;
  155. else
  156. l=mid+1;
  157. }
  158. printf("%lld\n",l*cntw-sumw);
  159. }
  160. void solve(){
  161. if(cntw!=cntb){
  162. PLAN1();
  163. }
  164. else{
  165. if(sumw!=sumb){
  166. printf("-1\n");
  167. return;
  168. }
  169. else
  170. PLAN2();
  171. }
  172. }
  173. int main(){
  174. freopen("bzoj.in","r",stdin);
  175. freopen("out.out","w",stdout);
  176. scanf("%lld",&kase);
  177. while(kase--){
  178. INIT();
  179. solve();
  180. }
  181. return 0;
  182. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注