Gold Transportation
Time Limit:2000MSMemory Limit:65536K
Total Submissions:3079Accepted:1101
Description
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
43 2 0 00 0 3 361 2 41 3 101 4 122 3 62 4 83 4 50
Sample Output
6
题意：
题意：有N个城市，每个城市都有一个金矿和一个仓库，，已给出每个城市金矿的容量以及仓库的空间。因为一个城市的仓库可能无法容纳该城市的所有金矿，所以需要通过运输方式把多余的金矿存储在其它城市的仓库里面。现在给你M条无向的运输路线以及路线的长度。问你能不能使得所有金矿都能存储在仓库里面，若不能输出No Solution，否则求出运输过程中（可能不需要运输）所有被使用路线中的最大长度 的最小值。
解析：又是最大值的最小值，好把，二分走起。二分枚举使用路线的最大长度mid，再枚举每一条边，边的权值满足 <= mid 的边加入新图，然后跑最大流，看是否满流，满流的话减少mid， 反之增加mid，最后得到就是所有被使用路线中的最大长度 的最小值。
具体建图过程：
（1）建立超级源点0， 超级汇点n + 1.
（2）汇点到每一个城市建边，权值为每个城市金矿的数量。
（3）枚举每一条边，边的权值满足 <= mid 的建边，权值为INF
（4）每个城市到汇点建边，权值为每个城市仓库的数量。
#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#define maxn 1000#define maxm 100000#define INF 0x3f3f3f3fusing namespace std;int n, m;int a[maxn];//每个城市的金矿数量int b[maxn];//每个城市的仓库数量struct NODE{int u, v, w, next;};NODE map[maxm];int head1[maxn], cnt1;void initmap(){cnt1 = 0;memset(head1, -1, sizeof(head1));}void addmap(int u ,int v, int w){map[cnt1].u = u;map[cnt1].v = v;map[cnt1].w = w;map[cnt1].next = head1[u];head1[u] = cnt1++;}int maxs;int sum;void input(){sum = maxs = 0;initmap();for(int i = 1; i <= n; ++i){scanf("%d", &a[i]);sum += a[i];}for(int i = 1; i <= n ;++i){scanf("%d", &b[i]);}scanf("%d", &m);while(m–){int a, b, c;scanf("%d%d%d", &a, &b, &c);maxs = max(maxs, c);addmap(a, b, c);addmap(b, a, c);}}struct node{int u, v, cap, flow, next;};node edge[maxm];int head[maxn], cnt, cur[maxn];int vis[maxn], dist[maxn];void initedge(){cnt = 0;memset(head, -1, sizeof(head));}void addedge(int u, int v, int w){edge[cnt].u = u;edge[cnt].v = v;edge[cnt].cap = w;edge[cnt].flow = 0;edge[cnt].next = head[u];head[u] = cnt++;edge[cnt].u = v;edge[cnt].v = u;edge[cnt].cap = 0;edge[cnt].flow = 0;edge[cnt].next = head[v];head[v] = cnt++;}void getmap(int ans){for(int i = 1; i <= n; ++i){addedge(0, i, a[i]);addedge(i, n + 1, b[i]);}for(int i = 0; i < cnt1; ++i)if(map[i].w <= ans)addedge(map[i].u, map[i].v, INF);}bool BFS(int st ,int ed){queue<int>q;memset(vis, 0 ,sizeof(vis));memset(dist, -1, sizeof(dist));vis[st] = 1;dist[st] = 0;q.push(st);while(!q.empty()){int u = q.front();q.pop();for(int i = head[u]; i != -1; i = edge[i].next){node E = edge[i];if(!vis[E.v] && E.cap > E.flow){vis[E.v] = 1;dist[E.v] = dist[u] + 1;if(E.v == ed)return true;q.push(E.v);}}}return false;}int DFS(int x, int ed, int a){if(x == ed || a == 0)return a;int flow = 0, f;for(int &i = cur[x]; i != -1; i = edge[i].next){node &E = edge[i];if(dist[E.v] == dist[x] + 1 && (f = DFS(E.v, ed, min(a, E.cap – E.flow))) > 0){E.flow += f;edge[i ^ 1].flow -= f;a -= f;flow += f;if(a == 0)break;}}return flow;}int maxflow(int st, int ed){int flowsum = 0;while(BFS(st,ed)){memcpy(cur, head, sizeof(head));flowsum += DFS(st, ed, INF);}return flowsum;}int main (){while(scanf("%d", &n), n){input();int l = 0, r = maxs, mid;int max_min = maxs;while(r > l){mid = (l + r) / 2;initedge();getmap(mid);if(maxflow(0, n + 1) == sum){max_min = min(max_min, mid);r = mid;}elsel = mid + 1;}if(max_min == maxs)printf("No Solution\n");elseprintf("%d\n", max_min);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
但我们好多人没想过，勇敢的冷静的理智的去接受失败，
