本文共 1721 字，大约阅读时间需要 5 分钟。
分析
第一问就是最大流
第二问用一个源点向1连一条流量为第一问答案+k的边然后跑费用流即可
代码
#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;const int inf = 1e9+7;int n,m,k;int s,t,Ans,now,sum; int head[300100],w[300100],c[300100],nxt[300100],to[300100];int fm[300100],ano[300100],S;inline void add(int x,int y,int z,int cost){ nxt[++S]=head[x];head[x]=S;to[S]=y;w[S]=z;c[S]=cost;fm[S]=x; nxt[++S]=head[y];head[y]=S;to[S]=x;w[S]=0;c[S]=-cost;fm[S]=y; ano[S]=S-1;ano[S-1]=S;}inline int work(int x){ int i,j,k=0; for(i=2;i<=sqrt(x);i++) while(x%i==0)x/=i,k++; if(x>1)k++; return k;}queue q;int iq[100100],nf[100100],la[100100],d[100100];inline void go(){ int i,j,k; la[s]=0; while(1){ for(i=1;i<=t;i++)d[i]=inf; q.push(s); d[s]=0,nf[s]=inf,iq[s]=1; while(!q.empty()){ int u=q.front(); q.pop(),iq[u]=0; for(i=head[u];i;i=nxt[i]) if(w[i]&&d[to[i]]>d[u]+c[i]){ d[to[i]]=d[u]+c[i]; la[to[i]]=i; nf[to[i]]=min(w[i],nf[u]); if(!iq[to[i]]){ q.push(to[i]); iq[to[i]]=1; } } } int be=now,ans=Ans,i=la[t]; if(!nf[t]||d[t]==inf)return; while(i){ w[i]-=nf[t]; w[ano[i]]+=nf[t]; now+=nf[t]*c[i]; i=la[fm[i]]; } Ans+=nf[t]; }}int a[11000],b[11000],C[11000],D[11000];signed main(){ int i,j; scanf("%d%d%d",&n,&m,&k); s=1,t=n; for(i=1;i<=m;i++){ scanf("%d%d%d%d",&a[i],&b[i],&C[i],&D[i]); add(a[i],b[i],C[i],0); } go(); printf("%d ",Ans); memset(head,0,sizeof(head)); S=0; for(i=1;i<=m;i++)add(a[i],b[i],C[i],0),add(a[i],b[i],inf,D[i]); s=n+1; add(s,1,Ans+k,0); now=Ans=0; go(); printf("%d\n",now); return 0;}
转载于:https://www.cnblogs.com/yzxverygood/p/10356739.html