POJ 2455 Secret Milking Machine (二分 + 最大流)

题目大意：

给出一张无向图，找出T条从1..N的路径，互不重复，求走过的所有边中的最大值最小是多少。

算法讨论：

首先最大值最小就提醒我们用二分，每次二分一个最大值，然后重新构图，把那些边权符合要求的边加入新图，在新图上跑网络流。

这题有许多注意的地方：

1、因为是无向图，所以我们在加正向边和反向边的时候，流量都是1，而不是正向边是1，反向边是0。

2、题目中说这样的路径可能不止t条，所以我们在最后二分判定的时候不能写 == t，而是要 >= t。

3、这题很容易T ，表示我T了N遍，弱菜啊。

Codes：

  1 #include <cstring>
  2 #include <cstdlib>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <cstdio>
  6 #include <vector>
  7 #include <queue>
  8 
  9 using namespace std;
 10 
 11 struct Edge{
 12     int from, to, cap, flow;
 13     Edge(int _from = 0, int _to = 0, int _cap = 0, int _flow = 0): 
 14         from(_from), to(_to), cap(_cap), flow(_flow) {}
 15 }E[40000 + 5];
 16 
 17 struct Dinic{
 18     static const int N = 200 + 5;
 19     static const int M = 80000 + 5; 
 20     static const int oo = 0x3f3f3f3f;
 21     
 22     int n, m, s, t;
 23     vector <Edge> edges;
 24     vector <int> G[N];
 25     int dis[N], cur[N];
 26     bool vi[N];
 27     
 28     void Clear(){
 29         for(int i = 1; i <= n; ++ i) G[i].clear();
 30         edges.clear();
 31     }
 32     
 33     void Add(int from, int to, int cap, int flow){
 34         edges.push_back((Edge){from, to, cap, 0});
 35         edges.push_back((Edge){to, from, cap, 0});
 36         int m = edges.size();
 37         G[from].push_back(m - 2);
 38         G[to].push_back(m - 1);
 39     }
 40     
 41     bool bfs(){
 42         for(int i = 1; i <= n; ++ i) vi[i] = false;
 43         dis[s] = 0; vi[s] = true;
 44         queue <int> q; q.push(s);
 45         
 46         while(!q.empty()){
 47             int x = q.front(); q.pop();
 48             for(int i = 0; i < G[x].size(); ++ i){
 49                 Edge &e = edges[G[x][i]];
 50                 if(!vi[e.to] && e.cap > e.flow){
 51                     vi[e.to] = true;
 52                     dis[e.to] = dis[x] + 1;
 53                     q.push(e.to);
 54                 }
 55             }
 56         }
 57         return vi[t];
 58     }
 59     
 60     int dfs(int x, int a){
 61         if(x == t || a == 0) return a;
 62         int flw = 0, f;
 63         for(int &i = cur[x]; i < G[x].size(); ++ i){
 64             Edge &e = edges[G[x][i]];
 65             if(dis[x] + 1 == dis[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0){
 66                 e.flow += f; edges[G[x][i]^1].flow -= f;
 67                 a -= f; flw += f;
 68                 if(!a) break;
 69             }
 70         }
 71         return flw;
 72     }
 73     
 74     int Maxflow(int s, int t){
 75         this->s = s;this-> t = t;
 76         int flw = 0;
 77         while(bfs()){
 78             memset(cur, 0, sizeof cur);
 79             flw += dfs(s, oo);
 80         }
 81         return flw;
 82     }
 83     
 84 }Net;
 85 
 86 int ns, ps, ts;
 87 int l = 0x3f3f3f3f, r, mid;
 88 
 89 bool check(int mv){
 90     for(int i = 0; i < ps; ++ i){
 91         if(E[i].cap <= mv){
 92             Net.Add(E[i].from, E[i].to, 1, 0);
 93         }
 94     }
 95     return Net.Maxflow(1, Net.n) >= ts;
 96 }
 97 
 98 int Solve(){
 99     int ans;
100     
101     while(l <= r){
102         Net.Clear();
103         mid = l + (r - l) / 2;    
104         if(check(mid)){
105             ans = mid; r = mid - 1;
106         }
107         else l = mid + 1;
108     }
109     
110     return ans;
111 }
112 
113 int main(){
114     int x, y, z;
115     
116     scanf("%d%d%d", &ns, &ps, &ts);
117     Net.n = ns;
118     for(int i = 0; i < ps; ++ i){
119         scanf("%d%d%d", &x, &y, &z);
120         E[i] = (Edge){x, y, z, 0};
121         l = min(l, z); r = max(r, z);
122     }
123     
124     printf("%d\n", Solve());
125     return 0;
126 }

让人更加不能理解的是，为什么我换了上面的邻接表的形式，用STL容器来存邻接表就AC，用数组来存就T成狗。

下面是我狂T的代码，良心网友们给查查错误呗。

  1 #include <cstdio>
  2     #include <iostream>
  3     #include <cstring>
  4     #include <cstdlib>
  5     #include <algorithm>
  6     #include <queue>
  7     
  8     using namespace std;
  9     
 10     int ns, ps, ts, te;
 11     int l=0x3f3f3f3f, r, Mid;
 12     
 13     struct Edge{
 14         int from, to, dt;
 15     }e[40000 + 5];
 16     
 17     struct Dinic{
 18       static const int maxn = 300 + 5;
 19       static const int maxm = 80000 + 5;
 20       static const int oo = 0x3f3f3f3f;
 21       
 22       int n,m,s,t;
 23       int tot;
 24       int first[maxn],next[maxm];
 25       int u[maxm],v[maxm],cap[maxm],flow[maxm];
 26       int cur[maxn],dis[maxn];
 27       bool vi[maxn];
 28       
 29       Dinic(){tot=0;memset(first,-1,sizeof first);}
 30       void Clear(){tot = 0;memset(first,-1,sizeof first);}
 31       void Add(int from,int to,int cp,int flw){
 32           u[tot] = from;v[tot] = to;cap[tot] = cp;flow[tot] = 0;
 33           next[tot] = first[u[tot]];
 34           first[u[tot]] = tot;
 35           ++ tot;
 36       }
 37       bool bfs(){
 38           memset(vi,false,sizeof vi);
 39           queue <int> q;
 40           dis[s] = 0;vi[s] = true;
 41           q.push(s);
 42           
 43           while(!q.empty()){
 44           int now = q.front();q.pop();
 45           for(int i = first[now];i != -1;i = next[i]){
 46               if(!vi[v[i]] && cap[i] > flow[i]){
 47               vi[v[i]] = true;
 48               dis[v[i]] = dis[now] + 1;
 49               q.push(v[i]);
 50             }
 51           }
 52         }
 53         return vi[t];
 54       }
 55       int dfs(int x,int a){
 56           if(x == t || a == 0) return a;
 57           int flw=0,f;
 58           int &i = cur[x];
 59           for(i = first[x];i != -1;i = next[i]){
 60             if(dis[x] + 1 == dis[v[i]] && (f = dfs(v[i],min(a,cap[i]-flow[i]))) > 0){
 61               flow[i] += f;flow[i^1] -= f;
 62             a -= f;flw += f;
 63             if(a == 0) break;    
 64           }
 65         }
 66         return flw;
 67       }
 68       int MaxFlow(int s,int t){
 69           this->s = s;this->t = t;
 70           int flw=0;
 71           while(bfs()){
 72             memset(cur,0,sizeof cur);
 73           flw += dfs(s,oo);    
 74         }
 75         return flw;
 76       }
 77     }Net;
 78     
 79     bool check(int mid){
 80         Net.Clear();
 81         for(int i = 1; i <= ps; ++ i){
 82             if(e[i].dt <= mid){
 83                 Net.Add(e[i].from, e[i].to, 1, 0);
 84                 Net.Add(e[i].to, e[i].from, 1, 0);
 85             }
 86         }
 87         return Net.MaxFlow(1, Net.n) >= ts;
 88     }
 89     int Solve(){
 90         int ans;
 91         while(l <= r){
 92             Mid = l + (r - l) / 2;
 93             if(check(Mid)){
 94                 ans = Mid; r = Mid - 1;
 95             }
 96             else l = Mid + 1;
 97         }
 98         return ans;
 99     }
100     int main(){
101         int x, y, z;
102         scanf("%d%d%d", &ns, &ps, &ts);
103         Net.n = ns;te = 0;
104         for(int i = 1; i <= ps; ++ i){
105             scanf("%d%d%d", &x, &y, &z);
106             ++ te;
107             e[te].from = x;e[te].to = y;e[te].dt = z;
108             l = min(l, z); r = max(z, r);
109         }
110         printf("%d\n", Solve());    
111         return 0;
112     }