poj 3228 Gold Transportation

                                                               Gold Transportation

题目链接：Click Here~

题目分析：

    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".

   题目理解没什么难得，主要是这一句的理解。翻译白话后其实就是：从起点可以到终点的n个方案中，得到每个方案中最长的那条路x，即n个方案可以得到（x1,x2,x3......xn）。而这条路满足是这n个方案中最小的那个，

即min(x1,x2,x3,.....xn)。

算法分析：

    我们知道这道题中有多个源点和汇点。所以，我们要建立一个超级源点和超级汇点。然后，每次二分最长路。用最大流判断当前的最长路是否满足。其他细节自己看代码吧。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 200+5;
const int INF = 10001;
struct Edge{
   int from,to,cap,flow;
};
vector<Edge> edges;
vector<int> G[maxn];
bool vst[maxn];
int d[maxn];
int cur[maxn];
int gold[maxn],store[maxn],graph[maxn][maxn];
int scoure,sink,n;
void Init()
{
    for(int i = 0;i <= n+1;++i)
        G[i].clear();
    edges.clear();
    memset(d,0,sizeof(d));
}
void AddEdge(int from,int to,int cap)
{
    edges.push_back((Edge){from,to,cap,0});
    edges.push_back((Edge){to,from,0,0});
    int sz = edges.size();
    G[from].push_back(sz-2);
    G[to].push_back(sz-1);
}
void Build(int num)
{
    Init();
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= n;++j)
          if(graph[i][j]<=num)
             AddEdge(i,j,INF);
    for(int i = 1;i <= n;++i)
        AddEdge(scoure,i,gold[i]);
    for(int i = 1;i <= n;++i)
        AddEdge(i,sink,store[i]);
}
bool BFS()     //xun zhao ceng ci tu
{
    memset(vst,false,sizeof(vst));
    queue<int> Q;
    Q.push(scoure);
    d[scoure] = 0;
    vst[scoure] = 1;
    while(!Q.empty()){
        int x = Q.front();
        Q.pop();
        for(int i = 0;i < G[x].size();++i){
            Edge& e = edges[G[x][i]];
            if(!vst[e.to]&&e.cap>e.flow){
                vst[e.to] = 1;
                d[e.to] = d[x] + 1;
                Q.push(e.to);
            }
        }
    }
    return vst[sink];
}
int DFS(int x,int a)
{
    if(x==sink||a==0)
        return a;
    int f,flow = 0;
    for(int& i = cur[x];i < G[x].size();++i){
        Edge& e = edges[G[x][i]];
        if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){
            e.flow += f;
            edges[G[x][i]^1].flow -= f;
            flow += f;
            a -= f;
            if(a==0)break;
        }
    }
    return flow;
}
int Maxflow()
{
    int flow = 0;
    while(BFS()){
        memset(cur,0,sizeof(cur));
        flow += DFS(scoure,INF);
    }
    return flow;
}
int main()
{
    while(scanf("%d",&n),n)
    {
        int sum = 0,tot = 0;
        for(int i = 0;i <= n;++i)
            for(int j = 0;j <= n;++j)
               graph[i][j] = INF;
        for(int i = 1;i <= n;++i){
            scanf("%d",&gold[i]);
            sum += gold[i];
        }
        for(int i = 1;i <= n;++i){
            scanf("%d",&store[i]);
            tot += store[i];
        }
        if(sum > tot){
            puts("No Solution");
            continue;
        }
        int m,x,y,d,maxv = -1,minv = INF;
        scanf("%d",&m);
        for(int i = 0;i < m;++i){
            scanf("%d%d%d",&x,&y,&d);
            graph[x][y] = graph[y][x] = d;
            maxv = max(maxv,d);
            minv = min(minv,d);
        }
        scoure = 0,sink = n+1;
        int ans=-1,low = minv,high = maxv;
        while(low <= high){
            int mid = (low+high)>>1;
            Build(mid);
            int tmp = Maxflow();
            if(tmp >= sum){
                ans = mid;
                high = mid -1;
            }
            else
                low = mid + 1;
        }
        if(ans>0)
          printf("%d\n",ans);
        else
          puts("No Solution");
    }
    return 0;
}

poj 3228 Gold Transportation,布布扣,bubuko.com

poj 3228 Gold Transportation

原文：http://blog.csdn.net/zhongshijunacm/article/details/22200595