poj 2391

无向图中给出N个点，M条边，每个点有当前囤积流量和最大容量，任意两个点之间有距离，首先保证所有的流量都可以被节点吸收（即不超过最大容量），然后将流量跑的最大距离限制到最小。
拆点：
然后二分答案。跟poj 2112差不多。
View Code
  1 // File Name: 2391.cpp
  2 // Author: Missa
  3 // Created Time: 2013/4/17 星期三 0:02:23
  4 
  5 #include<iostream>
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<algorithm>
  9 #include<cmath>
 10 #include<queue>
 11 #include<stack>
 12 #include<string>
 13 #include<vector>
 14 #include<cstdlib>
 15 #include<map>
 16 #include<set>
 17 using namespace std;
 18 #define CL(x,v) memset(x,v,sizeof(x));
 19 #define R(i,st,en) for(int i=st;i<en;++i)
 20 #define LL long long
 21 
 22 const LL INF = 1e16;
 23 const int inf = 0x3f3f3f3f;
 24 const int maxn = 410;
 25 const int maxm = 160010;
 26 struct Edge
 27 {
 28     int v, c, next;//指向点,流量,下一个点
 29 }p[maxm << 1];
 30 int head[maxn], e;
 31 int d[maxn], cur[maxn];//层次记录，当前弧优化
 32 int n, m, st, en;
 33 void init()
 34 {
 35     e = 0;
 36     memset(head, -1, sizeof(head));
 37 }
 38 void addEdge(int u, int v, int c)
 39 {
 40     p[e].v = v; p[e].c = c; 
 41     p[e].next = head[u];head[u] = e++;
 42     p[e].v = u; p[e].c = 0; //无向图时逆边赋值流量cap，有向图时赋值0.
 43     p[e].next = head[v];head[v] = e++;
 44 }
 45 int bfs(int st, int en)
 46 {
 47     queue <int> q;
 48     memset(d, 0, sizeof(d));
 49     d[st] = 1;
 50     q.push(st);
 51     while (!q.empty())
 52     {
 53         int u = q.front(); q.pop();
 54         for (int i = head[u]; i != -1; i = p[i].next)
 55         {
 56             if (p[i].c > 0 && !d[p[i].v])
 57             {
 58                 d[p[i].v] = d[u] + 1;
 59                 q.push(p[i].v);
 60             }
 61         }
 62     }
 63     return d[en];
 64 }
 65 int dfs(int u, int a)//a表示流量
 66 {
 67     if (u == en || a == 0) return a;
 68     int f, flow = 0;
 69     for (int& i = cur[u]; i != -1; i = p[i].next)
 70     {
 71         if (d[u] + 1 == d[p[i].v] && (f = dfs(p[i].v,min(a,p[i].c))) > 0)
 72         {
 73             p[i].c -= f;
 74             p[i^1].c += f;
 75             flow += f;
 76             a -= f;
 77             if (!a) break;
 78         }
 79     }
 80     return flow;
 81 }
 82 int dinic(int st, int en)
 83 {
 84     int res = 0;
 85     while (bfs(st, en))
 86     {
 87         for (int i = 0; i <= n; ++i)
 88             cur[i] = head[i];
 89         res += dfs(st, inf);
 90     }
 91     return res;
 92 }
 93 int w[maxn], c[maxn], tt; 
 94 LL a[maxn][maxn];
 95 void rebuild(LL mid)
 96 {
 97     init();
 98     for (int i = 1; i <= tt; ++i)
 99     {
100         addEdge(st, i, w[i]);
101         addEdge(i + tt, en, c[i]);
102     }
103     for (int i = 1; i <= tt; ++i)
104         addEdge(i, i + tt, inf);
105     for (int i = 1; i <= tt; ++i)
106     {
107         for (int j = i + 1; j <= tt; ++j)
108             if (a[i][j] <= mid)
109             {
110                 addEdge(i, j + tt, inf);
111                 addEdge(j, i + tt, inf);
112             }
113     }
114 }
115 int main()
116 {
117     while(~scanf("%d%d",&n,&m))
118     {
119         tt = n;
120         st = 0; en = (n << 1) + 1;
121         int sum = 0;
122         for (int i = 1; i <= n; ++i)
123         {
124             scanf("%d%d",&w[i], &c[i]);
125             sum += w[i];
126         }
127         for (int i = 1; i <= n; ++i)
128             for (int j = 1; j <= n; ++j)
129                 a[i][j] = INF;
130         //cout <<a[n][n] + a[n][n]<<endl;
131         for (int i = 1; i <= m; ++i)
132         {
133             int uu, vv, len;
134             scanf("%d%d%d", &uu, &vv, &len);
135             if (len < a[uu][vv])
136                 a[uu][vv] = a[vv][uu] = len;
137         }
138         for (int k = 1; k <= n; ++k)
139             for (int i = 1; i <= n; ++i)
140                 for (int j = 1; j <= n; ++j)
141                     if (a[i][j]  > a[i][k] + a[k][j])
142                         a[i][j] = a[i][k] + a[k][j];
143         LL ans = -1, low = 0, high = INF - 1;
144         n = en;
145         while (low <= high)
146         {
147             LL mid = (low + high) / 2;
148             //cout << mid <<endl;
149             rebuild(mid);
150             int tmp = dinic(st, en);
151             //cout <<"mid = "<<mid<<" dinic = "<< tmp <<endl;
152             if (tmp >= sum)
153             {
154                 ans = mid;
155                 high = mid - 1;
156             }
157             else low = mid + 1;
158         }
159         printf("%I64d\n",ans);
160     }
161     return 0;
162 }