POJ 2391

题意：给出一张F个点P条路径的带权无向图，权值代表走这条路的时间。每个点F上现在有a头牛，而每个点最多可容纳b头牛，问是否存在一种调整方案使得所有的点上存在的牛数少于该点容纳牛数的上限，如果可以，输出最短时间，否则，输出-1。

思路：拆点，二分。先做一遍floyd。把每个点拆成i,i'，有边(i,i',inf)。二分枚举时间t，如果可以在t时间内从i走到j，那么从i到j’连一条边(i,j',inf)。跑最大流，如果满流（就是maxflow=总牛数），即成立。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define INF 0x7fffffff
  6 #define maxn 410
  7 #define maxm 1<<17
  8 using namespace std;
  9 typedef long long LL;
 10 int v[maxm],next[maxm],w[maxm];
 11 int first[maxn],d[maxn],work[maxn],q[maxn];
 12 int e,S,T;
 13 LL f[maxn>>1][maxn>>1];
 14 int field[maxn>>1],shelter[maxn>>1];
 15 void init(){
 16     e = 0;
 17     memset(first,-1,sizeof(first));
 18 }
 19 
 20 void add_edge(int a,int b,int c){
 21     //printf("add:%d to %d,cap = %d
",a,b,c);
 22     v[e] = b;w[e] = c;next[e] = first[a];first[a] = e++;
 23     v[e] = a;w[e] = 0;next[e] = first[b];first[b] = e++;
 24 }
 25 
 26 int bfs(){
 27     int rear = 0;
 28     memset(d,-1,sizeof(d));
 29     d[S] = 0;q[rear++] = S;
 30     for(int i = 0;i < rear;i++){
 31         for(int j = first[q[i]];j != -1;j = next[j])
 32             if(w[j] && d[v[j]] == -1){
 33                 d[v[j]] = d[q[i]] + 1;
 34                 q[rear++] = v[j];
 35                 if(v[j] == T)   return 1;
 36             }
 37     }
 38     return 0;
 39 }
 40 
 41 int dfs(int cur,int a){
 42     if(cur == T)    return a;
 43     for(int &i = work[cur];i != -1;i = next[i]){
 44         if(w[i] && d[v[i]] == d[cur] + 1)
 45             if(int t = dfs(v[i],min(a,w[i]))){
 46                 w[i] -= t;w[i^1] += t;
 47                 return t;
 48             }
 49     }
 50     return 0;
 51 }
 52 
 53 int dinic(){
 54     int ans = 0;
 55     while(bfs()){
 56         memcpy(work,first,sizeof(first));
 57         while(int t = dfs(S,INF))   ans += t;
 58     }
 59     return ans;
 60 }
 61 
 62 int main()
 63 {
 64     int F,P;
 65     scanf("%d%d",&F,&P);
 66     int sum = 0;
 67     for(int i = 1;i <= F;i++){
 68         scanf("%d%d",&field[i],&shelter[i]);
 69         sum += field[i];
 70     }
 71     for(int i = 1;i <= F;i++)
 72         for(int j = 1;j <= F;j++)   f[i][j] = INF * (LL)1000;
 73     for(int i = 1;i <= P;i++){
 74         int a,b;
 75         LL c;
 76         scanf("%d%d%lld",&a,&b,&c);
 77         f[a][b] = f[b][a] = min(f[a][b],c);
 78     }
 79     LL L = 0,R = -1,ans = -1;
 80     for(int k = 1;k <= F;k++)
 81     for(int i = 1;i <= F;i++)
 82     for(int j = 1;j <= F;j++){
 83         if(f[i][k] + f[k][j] < f[i][j])
 84             f[i][j] = f[i][k] + f[k][j],R = max(R,f[i][j]);
 85     }
 86     S = 0,T = 2*F+1;
 87     R += 100;
 88     while(L < R){
 89         LL mid = (L+R) >> 1LL;
 90         //printf("mid = %lld
",mid);
 91         init();
 92         for(int i = 1;i <= F;i++){
 93             add_edge(S,i,field[i]);
 94             add_edge(i,i+F,INF);
 95             add_edge(i+F,T,shelter[i]);
 96             for(int j = 1;j <= F;j++){
 97                 if(i == j)  continue;
 98                 if(f[i][j] != -1 && f[i][j] <= mid)
 99                     add_edge(i,j+F,INF);
100             }
101         }
102         int tmp = dinic();
103         //printf("tmp = %d
",tmp);
104         if(tmp == sum)  ans = R = mid;
105         else    L = mid+1;
106     }
107     printf("%lld
",ans);
108     return 0;
109 }

View Code