第一问直接最大流即可，记这个最大流为ans
第二问可以在原图的基础上，初始边费用为0，新增费用为w流量为inf的边，新增0号点向1流一条流量为ans+k，费用为0的边，跑最小费用最大流即可
考虑这个过程中，由于费用都为正，所以一定先走费用为0的边，相当于现求最大流，所以可以直接在残余网络上加入费用为w，流量为inf的边即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 1005 4 struct ji{ 5 int nex,to,len,cost; 6 }edge[N*20]; 7 queue<int>q; 8 int E,n,m,k,x,y,z,w,head[N],work[N],d[N],from[N],vis[N]; 9 void add(int x,int y,int z,int w){ 10 edge[E].nex=head[x]; 11 edge[E].to=y; 12 edge[E].len=z; 13 edge[E].cost=w; 14 head[x]=E++; 15 if (E&1)add(y,x,0,-w); 16 } 17 bool bfs(){ 18 memset(d,-1,sizeof(d)); 19 q.push(1); 20 d[1]=0; 21 while (!q.empty()){ 22 int k=q.front(); 23 q.pop(); 24 for(int i=head[k];i!=-1;i=edge[i].nex) 25 if ((edge[i].len)&&(d[edge[i].to]<0)){ 26 d[edge[i].to]=d[k]+1; 27 q.push(edge[i].to); 28 } 29 } 30 return d[n]>=0; 31 } 32 int dfs(int k,int s){ 33 if (k==n)return s; 34 int p; 35 for(int &i=work[k];i!=-1;i=edge[i].nex) 36 if ((edge[i].len)&&(d[edge[i].to]==d[k]+1)){ 37 p=dfs(edge[i].to,min(s,edge[i].len)); 38 if (p){ 39 edge[i].len-=p; 40 edge[i^1].len+=p; 41 return p; 42 } 43 } 44 return 0; 45 } 46 bool spfa(){ 47 memset(d,0x3f,sizeof(d)); 48 memset(vis,0,sizeof(vis)); 49 q.push(0); 50 d[0]=0; 51 while (!q.empty()){ 52 int k=q.front(); 53 q.pop(); 54 vis[k]=0; 55 for(int i=head[k];i!=-1;i=edge[i].nex){ 56 int v=edge[i].to; 57 if ((edge[i].len)&&(d[v]>d[k]+edge[i].cost)){ 58 d[v]=d[k]+edge[i].cost; 59 from[v]=i; 60 if (!vis[v]){ 61 vis[v]=1; 62 q.push(v); 63 } 64 } 65 } 66 } 67 return d[n]<0x3f3f3f3f; 68 } 69 int main(){ 70 scanf("%d%d%d",&n,&m,&k); 71 memset(head,-1,sizeof(head)); 72 for(int i=1;i<=m;i++){ 73 scanf("%d%d%d%d",&x,&y,&z,&w); 74 add(x,y,z,w); 75 } 76 int ans=0; 77 while (bfs()){ 78 memcpy(work,head,sizeof(head)); 79 while (x=dfs(1,0x3f3f3f3f))ans+=x; 80 } 81 printf("%d ",ans); 82 for(int i=0;i<m;i++){ 83 add(edge[i*2+1].to,edge[i*2].to,0x3f3f3f3f,edge[i*2].cost); 84 edge[i*2].cost=edge[i*2+1].cost=0; 85 } 86 add(0,1,k,0); 87 ans=0; 88 while (spfa()){ 89 x=0x3f3f3f3f; 90 for(int i=n;i;i=edge[from[i]^1].to)x=min(x,edge[from[i]].len); 91 ans+=x*d[n]; 92 for(int i=n;i;i=edge[from[i]^1].to){ 93 edge[from[i]].len-=x; 94 edge[from[i]^1].len+=x; 95 } 96 } 97 printf("%d",ans); 98 }