Cogs 739. [网络流24题] 运输问题(费用流)

[网络流24题] 运输问题 ★★ 输入文件：tran.in 输出文件：tran.out 简单对比 时间限制：1 s 内存限制：128 MB «问题描述： «编程任务： 对于给定的m 个仓库和n 个零售商店间运送货物的费用，计算最优运输方案和最差运 输方案。 «数据输入： «结果输出: 程序运行结束时，将计算出的最少运输费用和最多运输费用输出到文件tran.out中。 输入文件示例 输出文件示例 tran.in 2 3 220 280 170 120 210 77 39 105 150 186 122 tran.out 48500 69140 对于所有数据：1<=N,M<=100 /* 最大/最小费用流. */ #include<iostream> #include<cstdio> #include<queue> #include<cstring> #define MAXN 410 #define INF 1e9 using namespace std; int n,m,S,T,cut=1,minans,maxans,a[MAXN],b[MAXN],vis[MAXN],c[MAXN][MAXN],dis[MAXN],fa[MAXN],head[MAXN]; queue<int>q; struct data{int u,v,next,c,f;}e[MAXN*MAXN*6]; 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) { for(int i=S;i<=T;i++) dis[i]=INF;dis[S]=0; q.push(S); while(!q.empty()) { int u=q.front();q.pop();vis[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(vis[v]!=t) vis[v]=t,q.push(v); } } } return dis[T]!=INF; } void mincost() { int t=1,tmp,x; while(bfs(t)) { tmp=fa[T]; 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]; } minans+=dis[T]*x; } } bool bfs2(int t) { for(int i=S;i<=T;i++) dis[i]=-INF;dis[S]=0; q.push(S); while(!q.empty()) { int u=q.front();q.pop();vis[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(vis[v]!=t) vis[v]=t,q.push(v); } } } return dis[T]!=-INF; } void maxcost() { int t=1,tmp,x; while(bfs2(t)) { tmp=fa[T]; 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]; } maxans+=dis[T]*x; } } int main() { int x; freopen("tran.in","r",stdin); freopen("tran.out","w",stdout); n=read(),m=read();S=0,T=n+m+1; for(int i=1;i<=n;i++) a[i]=read(),add(S,i,a[i],0); for(int i=1;i<=m;i++) b[i]=read(),add(i+n,T,b[i],0); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) c[i][j]=read(),add(i,j+n,INF,c[i][j]); mincost(); memset(head,0,sizeof head); memset(e,0,sizeof e); for(int i=1;i<=n;i++) add(S,i,a[i],0); for(int i=1;i<=m;i++) add(i+n,T,b[i],0); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) add(i,j+n,INF,c[i][j]); maxcost(); printf("%d %d",minans,maxans); return 0; }