BZOJ5228: [Lydsy2017省队十连测]Bounce
? 解题记录 ? ? BZOJ ? ? 费用流 ? ? 网络流 ?    2018-10-01 10:03:10    536    0    0

很套路的一道题,做过无限之环来看这道题还是十分好想的

因为我比较菜,考试的时候就没能想出来。

按照套路,把格子黑白染色,然后考虑图的特点,到一个地方一定拐弯。

并且,对于一条回路来说,正向和反向的贡献都是一样的。

接下来,我们指定黑、白格子的流向,考虑一个白格子的流出一定是某个黑格子的流入。那么就好办了,我们规定黑格子横进竖出,白格子横出竖进。这样我们把问题抽象成一张图,对于每一个格子可以选择从进向自己连边,自己向出连边,相当于每种进的方案都可以选择两种出去的方案。但是题目还有一个隐含条件,一个点只能经过一条流量,也就是出入度都是1,想到限制出入度便想到了最小路劲覆盖的模型。

于是,初步的构图便完成了。

1、套用最小路径覆盖模型把每一个格子拆两个点u1, u2。S->u1->u2->T费用都是0,流量都是1,考虑到一个格子不经过的情况,相当于一个自环,所以u1->u2有连边。

2、格子X的连边分为:1、黑色,左右两边是A, B,A1->X2, B1->X2,上下两边是C, D,X1->C2,X1->D2。2、白色,把上面的连边反过来X1->A2, X1->B2, C1->X2, D1->X2

最后,对于必须走的格子,也就是不能有自环,我们去掉中间u1->u2的边即可。

 

辣鸡题目卡我常数……

把TLE的点删了下面的程序就能过了

  1. #include<cstdio>
  2. #include<queue>
  3. #include<algorithm>
  4. #include<cstring>
  5. #include<iostream>
  6. #define LL long long
  7. using namespace std;
  8. const int maxm = 5e3 + 5;
  9. const int maxn = 2e3 + 5;
  10. const int N = 35;
  11. const int inf = 0x3f3f3f3f;
  12.  
  13. inline char gc(){
  14.     static char buf[5000000], *p1 = buf, *p2 = buf;
  15.     return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 5000000, stdin), p1 == p2) ? EOF : *p1++;
  16. }
  17. int f = 1;
  18. inline void read(int & x) {
  19.     x = 0, f = 1; static char c = gc();
  20.     while(!isdigit(c)) {
  21.      if(== '-') f = -1;
  22.      c = gc();
  23.     }
  24.     while(isdigit(c)) x = x * 10 + c - '0', c = gc();
  25.     x *= f;
  26. }
  27.  
  28. struct edge {
  29.     int v, w, cost, next;
  30. } e[maxm << 2];
  31. int head[maxn], cnt;
  32. void adde(const int &u, const int &v, const int &w, const int &cost) {
  33.     //cerr << u << "---" << w << "/" << cost << "-->" << v << endl;
  34.     e[cnt] = (edge) {v, w, cost, head[u]};
  35.     head[u] = cnt++;
  36.     e[cnt] = (edge) {u, 0, -cost, head[v]};
  37.     head[v] = cnt++;
  38. }
  39.  
  40. int q[maxn * maxn], frt, bk;
  41. int vis[maxn], fa[maxn], fw[maxn], id[maxn], dis[maxn];
  42. LL dw;
  43. const int Lf = 0, Rt = 1;
  44. int C[N][N], R[N][N], ban[N][N];
  45. int n, m, K, u, v, ND[N][N][2], dcnt, S, T;
  46.  
  47.  
  48. int SPFA(int s, int t) {
  49. frt = bk = 1;
  50.     q[bk++] = s, vis[s] = 1;
  51.     for(register int i = 1; i <= dcnt; ++i)
  52.      dis[i] = -inf;
  53.     dis[s] = 0;
  54.     while(frt < bk) {
  55.         int u = q[frt++];
  56.         vis[u] = 0;
  57.         for(register int i = head[u]; ~i; i = e[i].next) {
  58.             int v = e[i].v;
  59.             if(!e[i].w) continue;
  60.             if(dis[v] < dis[u] + e[i].cost) {
  61.                 dis[v] = dis[u] + e[i].cost;
  62.                 fa[v] = u, fw[v] = e[i].w, id[v] = i;
  63.                 if(vis[v]) continue;
  64.                 q[bk++] = v;
  65.                 vis[v] = 1;
  66.             }
  67.         }
  68.     }
  69.     return dis[t];
  70. }
  71.  
  72. int Flow(int u, int t, int mn) {
  73.     if(== t) return mn;
  74.     mn = Flow(fa[u], t, min(mn, fw[u]));
  75.     e[id[u]].-= mn, e[id[u] ^ 1].+= mn;
  76.     return mn;
  77. }
  78.  
  79. int MaxFlow(int s, int t) {
  80.     int ans = 0, f = 0, tmp;
  81.     while(SPFA(s, t) != -inf) {
  82.         tmp = Flow(t, s, inf), f += tmp;
  83.         ans += 1ll * dis[t] * tmp;
  84.     }
  85.     return f == dw ? ans : -1;
  86. }
  87.  
  88. int spc[* N][2];
  89.  
  90. int main() {
  91.     //freopen("bounce.in", "r", stdin);
  92.     //freopen("bounce.out", "w", stdout);
  93.     int t;
  94.     read(t);
  95.     while(t--) {
  96.     memset(head, -1, sizeof(head));
  97.     memset(ban, 0, sizeof(ban));
  98.     cnt = 0, dcnt = 0;
  99.     read(n), read(m), dw = n * m;
  100.     for(register int i = 1; i <= n; ++i)
  101.      for(register int j = 1; j < m; ++j)
  102.      read(C[i][j]);
  103.     for(register int i = 1; i < n; ++i)
  104.      for(register int j = 1; j <= m; ++j)
  105.      read(R[i][j]);
  106. read(K);
  107. for(register int i = 1; i <= K; ++i) {
  108. read(u), read(v);
  109. ban[u][v] = 1, spc[i][0] = u, spc[i][1] = v;
  110. } 
  111. = ++dcnt, T = ++dcnt;
  112.     for(register int i = 1; i <= n; ++i)
  113.      for(register int j = 1; j <= m; ++j) {
  114.      ND[i][j][Lf] = ++dcnt;
  115.      ND[i][j][Rt] = ++dcnt;
  116.      adde(S, ND[i][j][Lf], 1, 0);
  117.      if(!ban[i][j]) adde(ND[i][j][Lf], ND[i][j][Rt], 1, 0);
  118.      adde(ND[i][j][Rt], T, 1, 0);
  119.      }
  120.     for(register int i = 1; i <= n; ++i)
  121.      for(register int j = 1; j <= m; ++j) {
  122.      if((+ j) & 1) { //横进竖出 
  123.      if(< m) adde(ND[i][+ 1][Lf], ND[i][j][Rt], 1, C[i][j]);
  124.      if(> 1) adde(ND[i][- 1][Lf], ND[i][j][Rt], 1, C[i][- 1]);
  125.      if(< n) adde(ND[i][j][Lf], ND[+ 1][j][Rt], 1, R[i][j]);
  126.      if(> 1) adde(ND[i][j][Lf], ND[- 1][j][Rt], 1, R[- 1][j]);
  127. } else {   //竖进横出 
  128.      if(< m) adde(ND[i][j][Lf], ND[i][+ 1][Rt], 1, C[i][j]);
  129.      if(> 1) adde(ND[i][j][Lf], ND[i][- 1][Rt], 1, C[i][- 1]);
  130.      if(< n) adde(ND[+ 1][j][Lf], ND[i][j][Rt], 1, R[i][j]);
  131.      if(> 1) adde(ND[- 1][j][Lf], ND[i][j][Rt], 1, R[- 1][j]);
  132. }
  133.      }
  134. int ans = MaxFlow(S, T);
  135.     if(ans == -1) printf("Impossible\n");
  136.     else printf("%d\n", ans);
  137. }
  138.     return 0;
  139. }

甚至,我贴了份ZKW也没有过,mmp

  1. #include<cstdio>
  2. #include<queue>
  3. #include<algorithm>
  4. #include<cstring>
  5. #include<iostream>
  6. #define LL long long
  7. using namespace std;
  8. const int maxm = 1e4 + 5;
  9. const int maxn = 5e3 + 5;
  10. const int N = 40;
  11. const int inf = 0x3f3f3f3f;
  12.   
  13. inline char gc(){
  14.     static char buf[5000000], *p1 = buf, *p2 = buf;
  15.     return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 5000000, stdin), p1 == p2) ? EOF : *p1++;
  16. }
  17. int f = 1;
  18. inline void read(int & x) {
  19.     x = 0, f = 1; static char c = gc();
  20.     while(!isdigit(c)) {
  21.      if(== '-') f = -1;
  22.      c = gc();
  23.     }
  24.     while(isdigit(c)) x = x * 10 + c - '0', c = gc();
  25.     x *= f;
  26. } 
  27.  
  28. LL dw;
  29. const int Lf = 0, Rt = 1;
  30. int C[N][N], R[N][N], ban[N][N];
  31. int n, m, K, u, v, ND[N][N][2], dcnt;
  32.  
  33. namespace ZKW {
  34. bool vis[maxn];int dist[maxn];
  35. //解释一下各数组的含义:vis两个用处:spfa里的访问标记,増广时候的访问标记,dist是每个点的距离标号
  36. int s,t,ans=0;
  37. //s是起点,t是终点,ans是费用答案
  38. int nedge=-1,p[maxm << 2],c[maxm << 2],cc[maxm << 2],nex[maxm << 2],head[maxn];
  39. //这里是边表,解释一下各数组的含义:p[i]表示以某一点出发的编号为i的边对应点,c表示编号为i的边的流量,cc表示编号为i的边的费用,nex和head不说了吧。。。
  40. inline void addedge(int x,int y,int z,int zz){
  41.     p[++nedge]=y;c[nedge]=z;cc[nedge]=zz;nex[nedge]=head[x];head[x]=nedge;
  42. }
  43. inline void adde(int x, int y, int z, int zz){
  44. addedge(x, y, z, zz);
  45. addedge(y, x, 0, -zz);
  46. }
  47. //建边(数组模拟边表倒挂)
  48. int q[maxn * maxn], frt, bk;
  49. inline bool spfa(int s,int t){
  50.     memset(vis,0,sizeof vis),frt=bk=1;
  51.     for(int i=0;i<=dcnt;i++)dist[i]=1e9;dist[t]=0;vis[t]=1;
  52. //首先SPFA我们维护距离标号的时候要倒着跑,这样可以维护出到终点的最短路径
  53.     q[bk++]=t;
  54. //使用了SPFA的SLF优化(SLF可以自行百度或Google)
  55.     while(frt<bk){
  56.         int now=q[frt];++frt;
  57.         for(int k=head[now];k>-1;k=nex[k])if(c[k^1]&&dist[p[k]]>dist[now]-cc[k]){
  58. //首先c[k^1]是为什么呢,因为我们要保证正流,但是SPFA是倒着跑的,所以说我们要求c[k]的对应反向边是正的,这样保证走的方向是正确的
  59.             dist[p[k]]=dist[now]-cc[k];
  60. //因为已经是倒着的了,我们也可以很清楚明白地知道建边的时候反向边的边权是负的,所以减一下就对了(负负得正)
  61.             if(!vis[p[k]]){
  62.                 vis[p[k]]=1;
  63.                 q[bk++]=p[k];
  64.             }
  65.         }
  66.         vis[now]=0;
  67.     }
  68.     return dist[s]<1e9;
  69. //判断起点终点是否连通
  70. }
  71. inline int dfs(int x,int low){
  72. //这里就是进行増广了
  73.     if(x==t){vis[t]=1;return low;}
  74.     int used=0,a;vis[x]=1;
  75. //这边是不是和dinic很像啊
  76.     for(int k=head[x];k>-1;k=nex[k])if(!vis[p[k]]&&c[k]&&dist[x]-cc[k]==dist[p[k]]){
  77. //这个条件就表示这条边可以进行増广
  78.         a=dfs(p[k],min(c[k],low-used));
  79.         if(a)ans+=a*cc[k],c[k]-=a,c[k^1]+=a,used+=a;
  80. //累加答案,加流等操作都在这了
  81.         if(used==low)break;
  82.     }
  83.     return used;
  84. }
  85. inline int costflow(){
  86.     int flow=0; ans=0;
  87.     while(spfa(s,t)){
  88. //判断起点终点是否连通,不连通说明满流,做完了退出
  89.         vis[t]=1;
  90.         while(vis[t]){
  91.             memset(vis,0,sizeof vis);
  92.             flow+=dfs(s,1e9);
  93. //一直増广直到走不到为止(这样也可以省时间哦)
  94.         }
  95.     }
  96.     return flow == dw ? -ans : -1;//这里返回的是最大流,费用的答案在ans里
  97. }
  98.  
  99. }
  100.  
  101.  
  102. int main() {
  103. using namespace ZKW;
  104.     freopen("bounce.in", "r", stdin);
  105.     freopen("bounce.out", "w", stdout);
  106.     int T;
  107.     read(T);
  108.     while(T--) {
  109.         memset(nex,-1,sizeof(nex));
  110. memset(head,-1,sizeof(head));
  111.         memset(ban, 0, sizeof(ban));
  112.         nedge = -1, dcnt = 0;
  113.         read(n), read(m), dw = n * m;
  114.         for(register int i = 1; i <= n; ++i)
  115.             for(register int j = 1; j < m; ++j)
  116.                 read(C[i][j]);
  117.         for(register int i = 1; i < n; ++i)
  118.             for(register int j = 1; j <= m; ++j)
  119.                 read(R[i][j]);
  120.         read(K);
  121.         for(register int i = 1; i <= K; ++i) {
  122.             read(u), read(v);
  123.             ban[u][v] = 1;
  124.         } 
  125.         s = ++dcnt, t = ++dcnt;
  126.         for(register int i = 1; i <= n; ++i)
  127.             for(register int j = 1; j <= m; ++j) {
  128.                 ND[i][j][Lf] = ++dcnt;
  129.                 ND[i][j][Rt] = ++dcnt;
  130.                 adde(s, ND[i][j][Lf], 1, 0);
  131.                 if(!ban[i][j]) adde(ND[i][j][Lf], ND[i][j][Rt], 1, 0);
  132.                 adde(ND[i][j][Rt], t, 1, 0);
  133.             }
  134.         for(register int i = 1; i <= n; ++i)
  135.             for(register int j = 1; j <= m; ++j) {
  136.                 if((+ j) & 1) { //横进竖出 
  137.                     if(< m) adde(ND[i][+ 1][Lf], ND[i][j][Rt], 1, -C[i][j]);
  138.                     if(> 1) adde(ND[i][- 1][Lf], ND[i][j][Rt], 1, -C[i][- 1]);
  139.                     if(< n) adde(ND[i][j][Lf], ND[+ 1][j][Rt], 1, -R[i][j]);
  140.                     if(> 1) adde(ND[i][j][Lf], ND[- 1][j][Rt], 1, -R[- 1][j]);
  141.                 } else {          //竖进横出 
  142.                     if(< m) adde(ND[i][j][Lf], ND[i][+ 1][Rt], 1, -C[i][j]);
  143.                     if(> 1) adde(ND[i][j][Lf], ND[i][- 1][Rt], 1, -C[i][- 1]);
  144.                     if(< n) adde(ND[+ 1][j][Lf], ND[i][j][Rt], 1, -R[i][j]);
  145.                     if(> 1) adde(ND[- 1][j][Lf], ND[i][j][Rt], 1, -R[- 1][j]);
  146.                 }
  147.             }
  148.         int ans = costflow();
  149.         if(ans == -1) printf("Impossible\n");
  150.         else printf("%d\n", ans);
  151.     }
  152.     return 0;
  153. }

 

上一篇: LOJ#2585. 「APIO2018」新家

下一篇: BZOJ5219: [Lydsy2017省队十连测]最长路径

536 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航