首页 > 代码库 > [bzoj1834][ZJOI2010]network 网络扩容
[bzoj1834][ZJOI2010]network 网络扩容
来自FallDream的博客，未经允许，请勿转载，谢谢。
给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况下，1到N的最大流； 2、 将1到N的最大流增加K所需的最小扩容费用。
n<=1000 m<=5000
第一问不说了，就是送分的。
然后假设求出了最大流W，那么我们重新构图，从S向1号点连流量为W+k，费用为0的边，其它边都建两条，一条流量为原流量，费用为0，另一条流量INF，费用是对应的费用，最后n向T连边就行了。
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#define S 0#define T 1001#define INF 2000000000 using namespace std;inline 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 - ‘0‘;ch = getchar();} return x * f;}struct edge{int to,next,w,c;}e[25005],E[25005]; int n,m,k,head[T+5],cnt=1,d[T+5],ans=0,pi=0,W;bool mark[T+5],inq[T+5];deque<int> q;inline void ins(int f,int t,int w,int c){ e[++cnt]=(edge){t,head[f],w,c}; head[f]=cnt; e[++cnt]=(edge){f,head[t],0,-c};head[t]=cnt;}bool modlabel(){ for(int i=S;i<T;++i) d[i]=INF; d[T]=0;q.push_back(T);inq[T]=1; while(!q.empty()) { int x=q.front();q.pop_front(); for(int i=head[x];i;i=e[i].next) if(e[i^1].w&&d[x]+e[i^1].c<d[e[i].to]) { d[e[i].to]=d[x]+e[i^1].c; if(!inq[e[i].to]) { inq[e[i].to]=1; if(d[e[i].to]<d[q.size()?q.front():0]) q.push_front(e[i].to); else q.push_back(e[i].to); } } inq[x]=0; } for(int i=S;i<=T;i++) for(int j=head[i];j;j=e[j].next) e[j].c+=d[e[j].to]-d[i]; return pi+=d[S],d[S]<INF;}int dfs(int x,int f){ if(x==T) return ans+=pi*f,f; int used=0;mark[x]=1; for(int i=head[x];i;i=e[i].next) if(e[i].w&&!e[i].c&&!mark[e[i].to]) { int w=dfs(e[i].to,min(f-used,e[i].w)); used+=w;e[i].w-=w;e[i^1].w+=w; if(used==f) return f; } return used;}int main(){ n=read();m=read();k=read(); for(int i=1;i<=m;++i) { E[i].next=read();E[i].to=read(); E[i].w=read();E[i].c=read(); ins(E[i].next,E[i].to,E[i].w,0); } ins(S,1,INF,0);ins(n,T,INF,0); while(modlabel()) do memset(mark,0,sizeof(mark)); while(W=dfs(S,INF),ans+=W,W); printf("%d ",ans); memset(head,0,sizeof(head));cnt=1; ins(S,1,ans+k,0);ins(n,T,INF,0); ans=0;pi=0; for(int i=1;i<=m;++i) { ins(E[i].next,E[i].to,E[i].w,0); ins(E[i].next,E[i].to,INF,E[i].c); } while(modlabel()) do memset(mark,0,sizeof(mark)); while(dfs(S,INF)); printf("%d",ans); return 0;}
[bzoj1834][ZJOI2010]network 网络扩容
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。