POJ 2455 - Secret Milking Machine

2023-10-30 17:56:52

题目大意：给出一个N个点的无向图，中间有P条边，要求找出从1到n的T条通路，满足它们之间没有公共边，并使得这些通路中经过的最长的边的长度最短。两点之间允许有重边

数据范围：2 <= N <= 200， 1 <= P <= 40,000，1 <= T <= 200，1 <= 每条路的长度L <= 1,000,000

题目分析：

看到“最大值最小”的第一反应就是二分最大长度k，满足T条通路没有公共边的第一反应就是将每条边的容量赋为1然后跑一遍最大流。这样算法就出来了：读入并建图，二分最大长度k，将所有长度小于等于 k 的边的容量设为1，大于 k 的边容量设为0，然后以1为源点，n为汇点做一遍最大流，如果满足最大流大于等于T，则合要求继续二分，直至找出答案。

一开始在双向边建图的时候有点犹豫。毕竟网络流要求每条边必须要有反向边。最开始的想法是将每条双向边都拆成两条单向边，对每条单向边都建立一条长度为无穷大的反向边（无穷大是为了保证二分时赋初始容量都将它们为0），但是后来证明这种想法是错误的：因为题目要求每条边只能走一次，但是按我的想法每条边可以正向走一次，反向走一次，加上题目中允许有重边，就使情况变得更加复杂。后来我发现网络流的反向边不一定要初始容量为0——就算我将这一条双向边的两个方向按照网络流的一对反向边来建立，初始容量都允许为1，无论正着流还是反着流这条边所能允许的总容量必然只有0或1……然后就想通了（希望能给这里想不太清楚的同学们一点帮助）

然后这道题TLE到死……经过hockey指点才发现是我Dinic 写残了，应该到不能流的时候就退出但是我没有……改掉这一点之后，我加上当前弧优化的Dinic还是可以600+MS勉强AC的

PS：网上有些人说重新建立源点和汇点，并连接一条从源点到1的容量为T的边，其实丝毫没有必要，直接以1为源点是可以的

  1 //date 20140118
  2 #include <cstdio>
  3 #include <cstring>
  4 
  5 const int maxn = 205;
  6 const int maxm = 80005;
  7 const int INF = 0x7FFFFFFF;
  8 
  9 inline int getint()
 10 {
 11     int ans(0); char w = getchar();
 12     while(‘0‘ > w || w > ‘9‘)w = getchar();
 13     while(‘0‘ <= w && w <= ‘9‘)
 14     {
 15         ans = ans * 10 + w - ‘0‘;
 16         w = getchar();
 17     }
 18     return ans;
 19 }
 20 
 21 inline int min(int a, int b){return a < b ? a : b;}
 22 inline int max(int a, int b){return a > b ? a : b;}
 23 
 24 int n, m, T;
 25 int s, t;
 26 struct edge
 27 {
 28     int v, w, c, next;
 29 }E[maxm];
 30 int a[maxn];
 31 int now[maxn];
 32 int nedge;
 33 int lab[maxn];
 34 
 35 inline void add(int u, int v, int w, int c)
 36 {
 37     E[++nedge].v = v;
 38     E[nedge].c = c;
 39     E[nedge].w = w;
 40     E[nedge].next =  a[u];
 41     a[u] = nedge;
 42 }
 43 
 44 int maxl, minl;
 45 
 46 inline int label()
 47 {
 48     static int q[maxn];
 49     int l = 0, r = 1;
 50     memset(lab, 0xFF, sizeof lab);
 51     q[1] = s; lab[s] = 0;
 52     while(l < r)
 53     {
 54         int x = q[++l];
 55         for(int i = a[x]; i; i = E[i].next)
 56             if(E[i].c == 1 && lab[E[i].v] == -1)
 57             {
 58                 lab[E[i].v] = lab[x] + 1;
 59                 q[++r] = E[i].v;
 60             }
 61     }
 62     return lab[t] != -1;
 63 }
 64 
 65 int Dinic(int v, int f)
 66 {
 67     if(v == t)return f;
 68     int res = 0, w;
 69     for(int i = now[v]; i; i = now[v] = E[i].next)
 70         if((E[i].c == 1) && (f > 0) && (lab[v] + 1 == lab[E[i].v]) && (w = Dinic(E[i].v, min(f, E[i].c))))
 71         {
 72             E[i].c -= w;
 73             E[i ^ 1].c += w;
 74             f -= w;
 75             res += w;
 76             if(f == 0)break;
 77         }
 78     if(res == 0)lab[v] = -1;
 79     return res;
 80 }
 81 
 82 inline int max_flow()
 83 {
 84     int ans = 0;
 85     while(label())
 86     {
 87         for(int i = s; i <= t; ++i)now[i] = a[i];
 88         ans += Dinic(s, INF);
 89     }
 90     return ans;
 91 }
 92 
 93 inline bool check(int k)
 94 {
 95     for(int i = 2; i <= nedge; i += 2)
 96         if(E[i].w <= k)E[i].c = E[i ^ 1].c = 1; else E[i].c = E[i ^ 1].c = 0;
 97     int ans = max_flow();
 98     //printf("%d\n", ans);
 99     return ans >= T;
100 }
101 
102 inline int solve(int l, int r)
103 {
104     int mid;
105     while(l < r)
106     {
107         mid = (l + r) >> 1;
108         if(check(mid))r = mid;
109         else l = mid + 1;
110     }
111     return l;
112 }
113 
114 int main()
115 {
116     n = getint(); m = getint(); T = getint();
117     nedge = 1; maxl = 0; minl = INF;
118     s = 1; t = n;
119     int x, y, z;
120     for(int i = 1; i <= m; ++i)
121     {
122         x = getint(); y = getint(); z = getint();
123         add(x, y, z, 0);
124         add(y, x, z, 0);
125         maxl = max(maxl, z);
126         minl = min(minl, z);
127     }
128     int ans = solve(minl, maxl);
129     printf("%d\n", ans);
130     return 0;
131 }

小结：建图还是需要多加思考多加练习，代码模板也是需要不断完善的，加油~

POJ 2455 - Secret Milking Machine

码农公寓

相关文章