Cogs 13. 運輸問題4(費用流)

2019-11-08 01:55:21

字體：大中小

來源：轉載

供稿：網友

運輸問題4 ★★☆ 輸入文件：maxflowd.in 輸出文件：maxflowd.out 簡單對比時間限制：1 s 內存限制：128 MB 【問題描述】一個工廠每天生產若干商品，需運輸到銷售部門進行銷售。從產地到銷地要經過某些城鎮，有不同的路線可以行走，每條兩城鎮間的公路都有一定的流量限制。公路設有收費站，每通過一輛車，要交納過路費。請你計算，在不考慮其它車輛使用公路的前提下，如何使產地運輸到銷地的商品最多，并使費用最少。【輸入格式】輸入文件有若干行第一行，一個整數n，表示共有n個城市(2<=n<=100)，產地是1號城市，銷地是n號城市第二行，一個整數，表示起點城市第三行，一個整數，表示終點城市下面有n行,每行有2n個數字。第p行第2q?1,2q列的數字表示城鎮p與城鎮q之間有無公路連接。數字為0表示無，大于0表示有公路，且這兩個數字分別表示該公路流量和每車費用。【輸出格式】輸出文件有一行第一行，1個整數n，表示最小費用為n。【輸入輸出樣例】輸入文件名： maxflowd.in 6 1 6 0 0 1 3 5 10 0 0 0 0 0 0 0 0 0 0 0 0 5 7 0 0 0 0 0 0 0 0 0 0 0 0 2 8 0 0 0 0 0 0 1 3 0 0 0 0 3 5 0 0 2 4 0 0 0 0 0 0 2 6 0 0 0 0 0 0 0 0 0 0 0 0 輸出文件名：maxflowd.out 63 /*spfa連續最短路增廣.大概就是spfa跑一個最小費用然后不斷調節流量.用類似dinic的方法不斷找增廣費用路徑. */#include<iostream>#include<cstdio>#include<queue>#define MAXN 110#define INF 1e9using namespace std;int n,m,S,T,cut=1,head[MAXN],fa[MAXN],ans,dis[MAXN],b[MAXN];struct data{int u,v,next,f,c;}e[MAXN*MAXN];queue<int>q;int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f;}void add(int u,int v,int c,int f){ e[++cut].u=u;e[cut].v=v;e[cut].c=c;e[cut].f=f;e[cut].next=head[u];head[u]=cut; e[++cut].u=v;e[cut].v=u;e[cut].c=0;e[cut].f=-f;e[cut].next=head[v];head[v]=cut;}bool bfs(int t){ q.push(S); for(int i=0;i<=n;i++) dis[i]=INF;dis[S]=0; while(!q.empty()) { int u=q.front();q.pop();b[u]=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(dis[v]>dis[u]+e[i].f&&e[i].c) { dis[v]=dis[u]+e[i].f;fa[v]=i; if(b[v]!=t) b[v]=t,q.push(v); } } } return dis[T]!=INF;}void mincost(){ int t=1; while(bfs(t)) { int tmp=fa[T],x=INF; while(tmp) x=min(x,e[tmp].c),tmp=fa[e[tmp].u]; tmp=fa[T]; while(tmp) { e[tmp].c-=x; e[tmp^1].c+=x; tmp=fa[e[tmp].u]; } ans+=dis[T]*x; t++; } return ;}int main(){ freopen("maxflowd.in","r",stdin); freopen("maxflowd.out","w",stdout); int x,y; n=read();S=read(),T=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { x=read(),y=read(); if(x) add(i,j,x,y); } mincost();