题解：先在原网络上跑最大流，然后加上带费用的边跑费用流
高一的时候做这道题怎么想不到？
注意：maxn代表的不一定是同一个变量的范围
#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<queue>using namespace std;const int inf=1000000000;const int maxn=5009;int n,m,k;struct Edge{int from,to,cap,flow,cost;};vector<int>G[maxn];vector<Edge>edges;void Addedge(int x,int y,int z,int w){Edge e;e.from=x;e.to=y;e.cap=z;e.flow=0;e.cost=w;edges.push_back(e);e.from=y;e.to=x;e.cap=0;e.flow=0;e.cost=-w;edges.push_back(e);int c=edges.size();G[x].push_back(c-2);G[y].push_back(c-1);}int s,t,totn;queue<int>q;int inq[maxn];int d[maxn];int p[maxn];int Spfa(int &nowflow,int &nowcost){for(int i=1;i<=totn;++i){d[i]=inf;inq[i]=0;}q.push(s);inq[s]=1;d[s]=0;while(!q.empty()){int x=q.front();q.pop();inq[x]=0;for(int i=0;i<G[x].size();++i){Edge e=edges[G[x][i]];if((e.cap>e.flow)&&(d[x]+e.cost<d[e.to])){d[e.to]=d[x]+e.cost;p[e.to]=G[x][i];if(!inq[e.to]){inq[e.to]=1;q.push(e.to);}}}}if(d[t]==inf)return 0;int x=t,a=inf;while(x!=s){Edge e=edges[p[x]];a=min(a,e.cap-e.flow);x=e.from;}nowflow+=a;nowcost+=a*d[t];x=t;while(x!=s){edges[p[x]].flow+=a;edges[p[x]^1].flow-=a;x=edges[p[x]].from;}return 1;}int rx[maxn],ry[maxn],rf[maxn],rw[maxn];int ans,ans2;void Minit(){ans=ans2=0;for(int i=1;i<=n+1;++i)G[i].clear();edges.clear();while(!q.empty())q.pop();}int main(){scanf("%d%d%d",&n,&m,&k);Minit();for(int i=1;i<=m;++i){scanf("%d%d%d%d",&rx[i],&ry[i],&rf[i],&rw[i]);Addedge(rx[i],ry[i],rf[i],0);}totn=n;s=1;t=n;while(Spfa(ans,ans2));printf("%d ",ans);Addedge(n+1,1,k,0);totn=n+1;s=n+1;for(int i=1;i<=m;++i){Addedge(rx[i],ry[i],inf,rw[i]);}while(Spfa(ans,ans2));printf("%d\n",ans2);return 0;}
1834 [ZJOI2010]network 网络扩容
原文地址：https://www.cnblogs.com/zzyer/p/8454406.html