首页 > 代码库 > BZOJ 1834 ZJOI2010 network 网络扩容 Dinic+EK费用流
BZOJ 1834 ZJOI2010 network 网络扩容 Dinic+EK费用流
题目大意:给定一个n个点m条边的无向图,每条边有一个扩容费用c,代表每扩容1流量的花费,求最大流及将最大流扩大k的最小费用
第一问直接跑最大流
第二问将每条边的起始点向终点连接一条流量为正无穷、费用为c的边 然后将n向汇点连一条流量为ans+k 费用为0的边 跑最小费用最大流即可
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 5010 #define INF 0x3f3f3f3f #define S 1 #define T (n+1) using namespace std; struct edge{ int x,y,f,c; }edges[M]; struct abcd{ int to,f,c,next; }table[M<<2]; int head[M],tot=1; int n,m,k,ans,anscost; int dpt[M]; void Add(int x,int y,int f,int c) { table[++tot].to=y; table[tot].f=f; table[tot].c=c; table[tot].next=head[x]; head[x]=tot; } bool BFS() { static int q[M],r,h; int i; memset(dpt,-1,sizeof dpt); r=h=0;q[++r]=S;dpt[S]=1; while(r!=h) { int x=q[++h]; for(i=head[x];i;i=table[i].next) if(table[i].f&&!~dpt[table[i].to]) { dpt[table[i].to]=dpt[x]+1; q[++r]=table[i].to; if(table[i].to==T) return true; } } return false; } int Dinic(int x,int flow) { int i,left=flow; if(x==T) return flow; for(i=head[x];i&&left;i=table[i].next) if(table[i].f&&dpt[table[i].to]==dpt[x]+1) { int temp=Dinic(table[i].to,min(left,table[i].f) ); if(!temp) dpt[table[i].to]=-1; left-=temp; table[i].f-=temp; table[i^1].f+=temp; } return flow-left; } bool EK() { static int q[65540],flow[M],cost[M],from[M]; static bool v[M]; static unsigned short r,h; int i; memset(cost,0x3f,sizeof cost); cost[S]=0;flow[S]=INF;q[++r]=S; while(r!=h) { int x=q[++h];v[x]=0; for(i=head[x];i;i=table[i].next) if(table[i].f) if(cost[table[i].to]>cost[x]+table[i].c) { cost[table[i].to]=cost[x]+table[i].c; flow[table[i].to]=min(flow[x],table[i].f); from[table[i].to]=i; if(!v[table[i].to]) v[table[i].to]=1,q[++r]=table[i].to; } } if(cost[T]==INF) return false; anscost+=flow[T]*cost[T]; for(i=from[T];i;i=from[table[i^1].to]) table[i].f-=flow[T],table[i^1].f+=flow[T]; return true; } int main() { int i; cin>>n>>m>>k; for(i=1;i<=m;i++) { scanf("%d%d",&edges[i].x,&edges[i].y); scanf("%d%d",&edges[i].f,&edges[i].c); Add(edges[i].x,edges[i].y,edges[i].f,0); Add(edges[i].y,edges[i].x,0,0); } Add(n,T,INF,0); Add(T,n,0,0); while( BFS() ) ans+=Dinic(S,INF); table[tot-1].f=k; for(i=1;i<=m;i++) { Add(edges[i].x,edges[i].y,INF,edges[i].c); Add(edges[i].y,edges[i].x,0,-edges[i].c); } while( EK() ); cout<<ans<<' '<<anscost<<endl; }
BZOJ 1834 ZJOI2010 network 网络扩容 Dinic+EK费用流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。