首页 > 代码库 > bzoj 1834: [ZJOI2010]network 网络扩容 -- 最大流+费用流
bzoj 1834: [ZJOI2010]network 网络扩容 -- 最大流+费用流
1834: [ZJOI2010]network 网络扩容
Time Limit: 3 Sec Memory Limit: 64 MBDescription
给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况下，1到N的最大流； 2、 将1到N的最大流增加K所需的最小扩容费用。
Input
输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。
Output
输出文件一行包含两个整数，分别表示问题1和问题2的答案。
Sample Input
5 8 2
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1
Sample Output
13 19
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
HINT
先跑一遍最大流
然后在残留网络建边对于每条边重新建一条容量inf的边（注意原边不变且费用为0）
然后就直接跑费用流
#include<map>#include<cmath>#include<queue>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define inf 100000007#define ll long long#define N 50010inline int rd(){ 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-‘0‘;ch=getchar();} return x*f;}int T;int fro[N],to[N],lj[N],v[N],w[N],fa[N],cnt=1,tw[N];void add(int a,int b,int c,int d){fro[++cnt]=lj[a];to[cnt]=b;fa[cnt]=a;v[cnt]=c;tw[cnt]=d;lj[a]=cnt;}void ins(int a,int b,int c,int d){add(a,b,c,d);add(b,a,0,-d);}int dis[N],q[N],from[N],ans,h,t;bool vs[N];bool bfs(){ memset(dis,0,sizeof(dis)); dis[1]=q[0]=t=1;h=0; int tp; while(h!=t) { tp=q[h++]; if(h==N) h=0; for(int i=lj[tp];i;i=fro[i]) { if(!dis[to[i]]&&v[i]) { dis[to[i]]=dis[tp]+1; q[t++]=to[i]; if(t==N) t=0; } } } return dis[T]?1:0;}int dfs(int x,int p){ if(x==T) return p; int tp,res=0; for(int i=lj[x];i;i=fro[i]) { if(v[i]&&dis[to[i]]==dis[x]+1) { tp=dfs(to[i],min(p-res,v[i])); v[i]-=tp; v[i^1]+=tp; res+=tp; if(res==p) return p; } } if(res==0) dis[x]=0; return res;}void dinic(){while(bfs()) ans+=dfs(1,inf);}bool spfa(){ memset(dis,0x3f,sizeof(dis)); int x; h=q[0]=dis[0]=0;t=vs[0]=1; while(h!=t) { x=q[h++]; if(h==N) h=0; for(int i=lj[x];i;i=fro[i]) { if(v[i]&&dis[to[i]]>dis[x]+w[i]) { dis[to[i]]=dis[x]+w[i]; from[to[i]]=i; if(!vs[to[i]]) { vs[to[i]]=1; q[t++]=to[i];if(t==N) t=0; } } } vs[x]=0; } return dis[T]<inf;}void qaz(){ int tmp=inf; for(int i=from[T];i;i=from[fa[i]]) tmp=min(tmp,v[i]); for(int i=from[T];i;i=from[fa[i]]) { v[i]-=tmp;v[i^1]+=tmp; ans+=w[i]*tmp; }}void add2(int a,int b,int c,int d){fro[++cnt]=lj[a];to[cnt]=b;fa[cnt]=a;v[cnt]=c;w[cnt]=d;lj[a]=cnt;}void ins2(int a,int b,int c,int d){add2(a,b,c,d);add2(b,a,0,-d);}void build(){ int tp=cnt; for(int i=2;i<=tp;i+=2) ins2(fa[i],to[i],inf,tw[i]);}int n,m,k,a,b,c,d;int main(){ T=n=rd();m=rd();k=rd(); for(int i=1;i<=m;i++) { a=rd();b=rd();c=rd();d=rd(); ins(a,b,c,d); } dinic(); printf("%d ",ans); ans=0;build(); ins(0,1,k,0); while(spfa()) qaz(); printf("%d\n",ans); return 0;}
bzoj 1834: [ZJOI2010]network 网络扩容 -- 最大流+费用流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。