[BZOJ1834]网络扩容 做题笔记

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1834
先跑一遍最大流，然后在原残量图的基础上建边。对原有的每条边，新建容量为inf，费用为题目描述的边。新建超级源S，S到1连一条容量为k费用为0的边，在新图上跑一遍费用流。

#include 
#include 
#include 
#include 
using namespace std;
const int N=2009,M=5109,inf=0x3fffffff;
int n,m,K;
int head[N],e[M<<2],ver[M<<2],c[M<<2],next[M<<2];
int ub[M],vb[M],wb[M],cb[M];
int pre[N],pos[N],d[N];bool vis[N];
int s,t,tot=1;void add (int u,int v,int w,int cost=0) {ver[++tot]=v;e[tot]=w;c[tot]=cost;next[tot]=head[u];head[u]=tot;ver[++tot]=u;e[tot]=0;c[tot]=-cost;next[tot]=head[v];head[v]=tot;
}bool spfa () {queue<int> q;memset(vis,0,sizeof(vis));memset(pre,-1,sizeof(pre));memset(pos,0,sizeof(pos));for (int i=0;i<=n+9;i++) d[i]=0x3fffffff; //注意这里，一开始我把n+9错写成了N+9，结果WA了q.push(s); d[s]=0; vis[s]=1; pre[s]=s;while (!q.empty()) {int x=q.front(); q.pop();for (int i=head[x];i;i=next[i]) if (e[i]&&d[x]+c[i]if (!vis[ver[i]]) q.push(ver[i]),vis[ver[i]]=1;}vis[x]=0;}return pre[t]!=-1;
}int mcf (bool opt) {int cost=0,maxflow=0,aug;while (spfa()) {aug=0x3fffffff;for (int i=t;i!=s;i=pre[i])  aug=min(aug,e[pos[i]]);maxflow+=aug,cost+=aug*d[t];for (int i=t;i!=s;i=pre[i]) e[pos[i]]-=aug,e[pos[i]^1]+=aug;}if (opt) return cost;return maxflow;
}int main () {scanf("%d%d%d",&n,&m,&K);for (int i=1;i<=m;i++) {scanf("%d%d%d%d",&ub[i],&vb[i],&wb[i],&cb[i]);add(ub[i],vb[i],wb[i]);}s=1,t=n;printf("%d ",mcf(0));s=0,t=n;add(s,1,K,0);for (int i=1;i<=m;i++) add(ub[i],vb[i],inf,cb[i]);printf("%d\n",mcf(1));
}

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