原題： In the latest Lab of IIUC, it requires to send huge amount of data from the local server to the terminal server. The lab setup is not yet ready. It requires to write a router PRogram for the best path of data. The problem is all links of the network has a fixed capacity and cannot flow more than that amount of data. Also it takes certain amount of time to send one unit data through the link. To avoid the collision at a time only one data unit can travel i.e. at any instant more than one unit of data cannot travel parallel through the network. This may be time consuming but it certainly gives no collision. Each node has sufficient buffering capability so that data can be temporarily stored there. IIUC management wants the shortest possible time to send all the data from the local server to the final one. 
For example, in the above network if anyone wants to send 20 unit data from A to D, he will send 10 unit data through AD link and then 10 unit data through AB-BD link which will take 10+70=80 unit time. Input Each input starts with two positive integers N (2 ≤ N ≤ 100), M (1 ≤ M ≤ 5000). In next few lines the link and corresponding propagation time will be given. The links are bidirectional and there will be at most one link between two network nodes. In next line there will be two positive integers D, K where D is the amount of data to be transferred from 1-st to N-th node and K is the link capacity. Input is terminated by EOF. Output For each dataset, print the minimum possible time in a line to send all the data. If it is not possible to send all the data, print ‘Impossible.’. The time can be as large as 10 15 . Sample Input 4 5 1 4 1 1 3 3 3 4 4 1 2 2 2 4 5 20 1 4 4 1 3 3 3 4 4 1 2 2 2 4 5 20 100 4 4 1 3 3 3 4 4 1 2 2 2 4 5 20 1 Sample Output Impossible. 140 Impossible.
中文： 給你一個無向圖，然后給你n個點和m條邊，每個邊有起點到終點，邊上的權值代表傳輸數據的代價，最后給你兩個數，d和k分別代表需要傳輸的總數據量和所有邊的容量。 問你能否從1到n節點完全傳達，如果能輸出最小代價。
#include<bits/stdc++.h>using namespace std;const int maxn=201;typedef long long ll;const ll LL_max=1+10e15;struct Edge//邊{ int from,to; ll cap,flow,cost;//出點，入點，容量，當前流量，費用（也就是權值） Edge(int u,int v,ll c,ll f,ll w):from(u),to(v),cap(c),flow(f),cost(w){}};struct MCMF{ int n,m; vector<Edge> edges;//保存表 vector<int> G[maxn];//保存鄰接關系 int inq[maxn];//判斷一個點是否在隊列當中（SPFA算法當中要用） long long d[maxn];//起點到d[i]的最短路徑保存值 int p[maxn];//用來記錄路徑，保存上一條弧 ll a[maxn];//找到增廣路徑后的改進量 void init(int n)//初始化 { this->n=n; for(int i=0;i<=n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap,long long cost)//添加邊 { edges.push_back(Edge(from,to,cap,0,cost));//正向 edges.push_back(Edge(to,from,0,0,-cost));//反向 m=edges.size(); G[from].push_back(m-2);//按照邊的編號保存鄰接關系 G[to].push_back(m-1); } bool BellmanFord(int s,int t,ll& flow,ll& cost)//最短路徑算法 { for(int i=0;i<=n;i++) d[i]=LL_max; memset(inq,0,sizeof(inq)); d[s]=0; inq[s]=1; p[s]=0; a[s]=LL_max; queue<int> Q; Q.push(s); while(!Q.empty()) { int u=Q.front(); Q.pop(); inq[u]=0; for(int i=0;i<G[u].size();i++) { Edge& e=edges[G[u][i]]; if(e.cap>e.flow&&d[e.to]>d[u]+e.cost)//尋找滿足容量大于流量的可松弛邊 { d[e.to]=d[u]+e.cost; p[e.to]=G[u][i]; a[e.to]=min(a[u],e.cap-e.flow); if(!inq[e.to])//是否在隊列當中 { Q.push(e.to); inq[e.to]=1; } } } } if(d[t]==LL_max)//如果d[t]沒有被更新，相當于沒找到增廣路徑，則沒有最大流也沒有最小費用 return false; flow+=a[t];//更新最大流 cost+=d[t]*a[t];//單位流量乘以單位路徑長度用來計算消耗 for(int u=t;u!=s;u=edges[p[u]].from)//通過使用p[]保存的上一個邊的值來對剛剛找到的增廣路徑上面的流量進行更新 { edges[p[u]].flow+=a[t];//正向變更新 edges[p[u]^1].flow-=a[t];//反向變更新（用位運算實現的） } return true; } ll MincostMaxflow(int s,int t,long long& cost)//計算從s到t的最小消耗cost，返回最大流 { ll flow = 0; cost=0; while(BellmanFord(s,t,flow,cost));//不斷尋找最短增廣路徑，直到找不到為止 return flow; }};MCMF mcmf;struct node{ int f,t,c;};int n,m,d,k;node tmp[5001];int main(){ ios::sync_with_stdio(false); while(cin>>n>>m) { for(int i=1;i<=m;i++) cin>>tmp[i].f>>tmp[i].t>>tmp[i].c; cin>>d>>k; mcmf.init(n+1); for(int i=1;i<=m;i++) { mcmf.AddEdge(tmp[i].f,tmp[i].t,k,tmp[i].c); mcmf.AddEdge(tmp[i].t,tmp[i].f,k,tmp[i].c); } mcmf.AddEdge(0,1,d,0); long long ans; ll flow=mcmf.MincostMaxflow(0,n,ans); if(flow<d) cout<<"Impossible."<<endl; else cout<<ans<<endl; } return 0;}思路： 我被模板題卡了一下午，樣例怎么都算不對，知道我用別人的代碼跑了一遍，才發現數據有錯誤！ 裸的最小費用最大流，注意雙向邊~
新聞熱點
疑難解答
