POJ 3228 Gold Transportation

Gold Transportation

Time Limit: 2000ms

Memory Limit: 65536KB

This problem will be judged on PKU. Original ID: 3228
64-bit integer IO format: %lld Java class name: Main

Recently, a number of gold mines have been discovered in Zorroming State. To protect this treasure, we must transport this gold to the storehouses as quickly as possible. Suppose that the Zorroming State consists of N towns and there are M bidirectional roads among these towns. The gold mines are only discovered in parts of the towns, while the storehouses are also owned by parts of the towns. The storage of the gold mine and storehouse for each town is finite. The truck drivers in the Zorroming State are famous for their bad temper that they would not like to drive all the time and they need a bar and an inn available in the trip for a good rest. Therefore, your task is to minimize the maximum adjacent distance among all the possible transport routes on the condition that all the gold is safely transported to the storehouses.

Input

The input contains several test cases. For each case, the first line is integer N(1<=N<=200). The second line is N integers associated with the storage of the gold mine in every towns .The third line is also N integers associated with the storage of the storehouses in every towns .Next is integer M(0<=M<=(n-1)*n/2).Then M lines follow. Each line is three integers x y and d(1<=x,y<=N,0<d<=10000), means that there is a road between x and y for distance of d. N=0 means end of the input.

Output

For each case, output the minimum of the maximum adjacent distance on the condition that all the gold has been transported to the storehouses or "No Solution".

Sample Input

Sample Output

Source

South Central China 2007 hosted by NUDT

解题：二分距离。求最小的最大距离。。。

源点与宝矿连接，容量为该矿的容量，汇点与藏点连接，容量为藏地的容量。矿和藏地的距离进行枚举

此题为什么如何建图，我还是有点不明白，奇葩的建图过程。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <climits>
  7 #include <vector>
  8 #include <queue>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <set>
 12 #include <stack>
 13 #define LL long long
 14 #define pii pair<int,int>
 15 #define INF 0x3f3f3f3f
 16 using namespace std;
 17 const int maxn = 210;
 18 struct arc {
 19     int to,flow,next;
 20     arc(int x = 0,int y = 0,int z = -1) {
 21         to = x;
 22         flow = y;
 23         next = z;
 24     }
 25 };
 26 arc e[maxn*maxn];
 27 int head[maxn],d[maxn],gold[maxn],store[maxn];
 28 int tot,n,m,S,T,cur[maxn],q[maxn],hd,tl;
 29 int a[maxn*maxn],b[maxn*maxn],c[maxn*maxn];
 30 void add(int u,int v,int w) {
 31     e[tot] = arc(v,w,head[u]);
 32     head[u] = tot++;
 33     e[tot] = arc(u,0,head[v]);
 34     head[v] = tot++;
 35 }
 36 void build(int mid) {
 37     memset(head,-1,sizeof(head));
 38     tot = 0;
 39     for(int i = 0; i < m; i++)
 40         if(c[i] <= mid) {
 41             add(a[i],b[i],INF);
 42             add(b[i],a[i],INF);
 43         }
 44     for(int i = 1; i <= n; i++)
 45         add(S,i,gold[i]);
 46     for(int i = 1; i <= n; i++)
 47         add(i,T,store[i]);
 48 }
 49 bool bfs() {
 50     memset(d,-1,sizeof(d));
 51     hd = tl = 0;
 52     q[tl++] = S;
 53     d[S] = 1;
 54     while(hd < tl) {
 55         int u = q[hd++];
 56         for(int i = head[u]; ~i; i = e[i].next) {
 57             if(d[e[i].to] == -1 && e[i].flow > 0) {
 58                 d[e[i].to] = d[u] + 1;
 59                 q[tl++] = e[i].to;
 60             }
 61         }
 62     }
 63     return d[T] > -1;
 64 }
 65 int dfs(int u,int low) {
 66     if(u == T) return low;
 67     int tmp = 0,a;
 68     for(int &i = cur[u]; ~i; i = e[i].next) {
 69         if(e[i].flow > 0 && d[e[i].to] == d[u] + 1 && (a = dfs(e[i].to,min(low,e[i].flow)))) {
 70             tmp += a;
 71             low -= a;
 72             e[i].flow -= a;
 73             e[i^1].flow += a;
 74             if(!low) break;
 75         }
 76     }
 77     if(!tmp) d[u] = -1;
 78     return tmp;
 79 }
 80 int dinic() {
 81     int tmp = 0;
 82     while(bfs()) {
 83         memcpy(cur,head,sizeof(head));
 84         tmp += dfs(S,INF);
 85     }
 86     return tmp;
 87 }
 88 int main() {
 89     int suma,sumb,high,low,ans;
 90     while(scanf("%d",&n),n) {
 91         suma = sumb = 0;
 92         for(int i = 1; i <= n; i++) {
 93             scanf("%d",gold+i);
 94             suma += gold[i];
 95         }
 96         for(int i = 1; i <= n; i++) {
 97             scanf("%d",store+i);
 98             sumb += store[i];
 99         }
100         scanf("%d",&m);
101         low = INF;
102         high = -1;
103         for(int i = 0; i < m; i++) {
104             scanf("%d %d %d",a+i,b+i,c+i);
105             low = min(low,c[i]);
106             high = max(high,c[i]);
107         }
108         if(suma > sumb) {
109             puts("No Solution");
110             continue;
111         }
112         ans = -1;
113         S = 0;
114         T = n + 1;
115         while(low <= high) {
116             int mid = (low + high)>>1;
117             build(mid);
118             if(dinic() >= suma) {
119                 ans = mid;
120                 high = mid - 1;
121             } else low = mid + 1;
122         }
123         if(ans > 0) printf("%d
",ans);
124         else puts("No Solution");
125     }
126     return 0;
127 }

View Code