第一问裸的最大流。
第二问给每一条边加上容量无限，费用为输入的边，新建起点终点，
新起点连1，费用为0，容量为ans1+k，新终点同理。
然后跑一边费用流。大功告成！
看代码：
#include<bits/stdc++.h> using namespace std; #define inf 1e9 const int maxn=1e5+10; int n,m,k; int beg1[maxn],nex1[maxn],to1[maxn],w1[maxn],e1; int beg2[maxn],nex2[maxn],to2[maxn],w2[maxn],cost[maxn],e2; inline void add1(int x,int y,int z){ nex1[e1]=beg1[x];beg1[x]=e1; to1[e1]=y;w1[e1]=z;e1++; } inline void add2(int x,int y,int z,int c){ nex2[e2]=beg2[x];beg2[x]=e2; to2[e2]=y;w2[e2]=z;cost[e2]=c;e2++; } inline int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*f; } int dep[maxn],dis[maxn],vis[maxn]; int flow[maxn],las[maxn],ed[maxn]; queue<int>q; inline int bfs(){ memset(dep,0x3f,sizeof(dep)); while(!q.empty())q.pop(); dep[1]=1;q.push(1); while(!q.empty()){ int x=q.front(); q.pop(); for(int i=beg1[x];~i;i=nex1[i]){ int t=to1[i]; if(w1[i]&&dep[t]>maxn){ dep[t]=dep[x]+1; q.push(t); } } } return dep[n]<=maxn; } inline int dfs(int x,int lim){ if(x==n||!lim)return lim; int ans=0; for(int i=beg1[x];~i;i=nex1[i]){ int t=to1[i]; if(w1[i]&&dep[t]==dep[x]+1){ int f=dfs(t,min(w1[i],lim)); ans+=f;lim-=f; w1[i]-=f;w1[i^1]+=f; } } return ans; } inline int spfa(){ memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); while(!q.empty())q.pop(); flow[0]=inf,dis[0]=0,vis[0]=1; las[0]=inf,las[n+1]=-1,q.push(0); while(!q.empty()){ int x=q.front(); q.pop();vis[x]=0; for(int i=beg2[x];~i;i=nex2[i]){ int t=to2[i]; if(w2[i]&&dis[t]>dis[x]+cost[i]){ dis[t]=dis[x]+cost[i]; las[t]=x;ed[t]=i; flow[t]=min(flow[x],w2[i]); if(!vis[t]){ vis[t]=1; q.push(t); } } } } return las[n+1]!=-1; } inline int calc(){ int tmp=n+1; while(tmp){ w2[ed[tmp]]-=flow[n+1]; w2[ed[tmp]^1]+=flow[n+1]; tmp=las[tmp]; } return flow[n+1]*dis[n+1]; } int main(){ memset(beg1,-1,sizeof(beg1)); memset(beg2,-1,sizeof(beg2)); n=read(),m=read(),k=read(); int x,y,z,c; for(int i=1;i<=m;i++){ x=read(),y=read(),z=read(),c=read(); add1(x,y,z),add1(y,x,0); add2(x,y,z,0),add2(y,x,0,0); add2(x,y,inf,c),add2(y,x,0,-c); } int maxflow=0,mincost=0; while(bfs())maxflow+=dfs(1,inf); add2(0,1,maxflow+k,0),add2(1,0,0,0); add2(n,n+1,maxflow+k,0),add2(n+1,n,0,0); while(spfa())mincost+=calc(); printf("%d %d ",maxflow,mincost); return 0; }
罕见的网络流写上100+行。