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; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。