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 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 200+5;
const int INF = 10001;
struct Edge{
   int from,to,cap,flow;
};
vector edges;
vector 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 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;
}