bzoj1834（网络流+费用流）

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况下，1到N的最大流； 2、 将1到N的最大流增加K所需的最小扩容费用。

第一问裸的网络流

第二问：新建一个汇点，将n号点与汇点相连，容量为k，（限制最多增大的流量）费用为0；

将原先每一条边都新建一个边，容量为inf，表示可以任意大的扩建，费用的该边扩展所需的费用，如果原先的那一条边没有满，那么费用流时肯定是走那条边

如果满了，就可能走扩展的边，同时cost一定的费用；

跑费用流

#include
#include
#include
#include
#include
#include
#include
#define debug(x) cout<<#x<<"="<'9') ch=getchar();ans=ch-'0';while ((ch=getchar())>='0'&&ch<='9') ans=ans*10+ch-'0';return ans;
}
void addedge(int x,int y,int z,int w)
{edge[++tot].to=y;edge[tot].pre=head[x];head[x]=tot;edge[tot].cap=z;edge[tot].w=w;edge[tot].from=x;
}
bool bfs()
{memset(lev,0,sizeof(lev));queue q;q.push(1);lev[1]=1;while(!q.empty()){int u=q.front();q.pop();for (int i=head[u];i;i=edge[i].pre)if (!lev[edge[i].to]&&edge[i].cap>edge[i].flow) {lev[edge[i].to]=lev[u]+1;if (edge[i].to==n) return true;q.push(edge[i].to);}}return false;
}
int dfs(int u,int maxflow)
{if (u==n||maxflow==0) return maxflow;int ans=0,&i=cur[u];for (;i;i=edge[i].pre)if (lev[edge[i].to]==lev[u]+1){int flow=dfs(edge[i].to,min(edge[i].cap-edge[i].flow,maxflow));ans+=flow;maxflow-=flow;edge[i].flow+=flow;edge[((i-1)^1)+1].flow-=flow;if (maxflow==0) return ans;}return ans;
}
int work1()
{int ans=0;while (bfs()) {for (int i=1;i<=n;i++) cur[i]=head[i];ans+=dfs(1,inf);	}return ans;
}
bool spfa()
{memset(pre,0,sizeof(pre));memset(b,false,sizeof(b));memset(dis,inf,sizeof(dis));memset(id,0,sizeof(id));pre[1]=-1;dis[1]=0;b[1]=true;queue q;q.push(1);while (!q.empty()){int u=q.front();q.pop();for (int i=head[u];i;i=edge[i].pre)if (dis[edge[i].to]>dis[u]+edge[i].w)if (edge[i].cap>edge[i].flow){dis[edge[i].to]=dis[u]+edge[i].w;pre[edge[i].to]=u;id[edge[i].to]=i;if (!b[edge[i].to]){b[edge[i].to]=true;q.push(edge[i].to);}}b[u]=false;}if (dis[t]==inf) return false;return true;
}
int work2()
{int ans=0,h=tot;for (int i=1;i<=h;i++) if (edge[i].cap>0)addedge(edge[i].from,edge[i].to,inf,ww[i]);//原先的正向边cap为infelse addedge(edge[i].from,edge[i].to,0,ww[i]);//反向边的cap应该为0，这里错了一次t=n+1;addedge(n,t,k,0);//限制扩容量while (spfa()){int flow=inf;for (int i=t;i!=1;i=pre[i])flow=min(flow,edge[id[i]].cap-edge[id[i]].flow);ans+=dis[t]*flow;for (int i=t;i!=1;i=pre[i])edge[id[i]].flow+=flow,edge[((id[i]-1)^1)+1].flow-=flow;}return ans;
}
int main()
{n=read();m=read();k=read();int x,z,y,w;while (m--){x=read();y=read();z=read();w=read();addedge(x,y,z,0);ww[tot]=w;addedge(y,x,0,0);ww[tot]=-w;}printf("%d ",work1());printf("%d",work2());return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！