第一问显然的最大流 第二问在残余网络上对于每条原来的边再连一条容量为 inf ，费用为 C[i] 的边。 然后建超级源点 S 向1连容量为 k 的边，n向超级汇点 T 连容量为k的边（我有强迫症）。 然后跑最小费用最大流。
#include <bits/stdc++.h> #define gc getchar() #define ll long long #define mid (l+r>>1) #define N 2009 #define M 50009 #define inf 0x3f3f3f3f using namespace std; int n,m,k,Ans=0; int X[M],Y[M],Z[M],C[M]; int number=1,pos,cur[N],dis[N]; bool vis[N]; vector<int> G[N]; struct edge { int from,to,flow,cap,cost; int rest() { return cap-flow; } void add(int x,int y,int z,int w) { from=x,to=y,cap=z,flow=0,cost=w; } }e[M]; void add(int x,int y,int z,int w) { e[++number].add(x,y,z,w); G[x].push_back(number); e[++number].add(y,x,0,-w); G[y].push_back(number); } #define E e[G[x][i]] bool bfs(int s,int t) { memset(vis,0,sizeof(vis)); queue<int> Q; Q.push(s); dis[s]=0; vis[s]=1; while (!Q.empty()) { int x=Q.front(); Q.pop(); for (int i=0;i<(int)G[x].size();i++) if (!vis[E.to]&&E.rest()>0) { vis[E.to]=1; dis[E.to]=dis[x]+1; Q.push(E.to); } } return vis[t]; } int dfs(int x,int a,int t) { if (x==t||a==0) return a; int flow=0,f; for (int &i=cur[x];i<(int)G[x].size();i++) if (dis[x]+1==dis[E.to]&&(f=dfs(E.to,min(a,E.rest()),t))>0) { E.flow+=f; e[G[x][i]^1].flow-=f; flow+=f; a-=f; if (!a) break; } return flow; } int Maxflow(int s,int t) { int flow=0; while (bfs(s,t)) { memset(cur,0,sizeof(cur)); flow+=dfs(s,inf,t); } return flow; } int pre[N]; void updata(int s,int t) { int f=inf; for (int i=t;i!=s;i=e[pre[i]].from) f=min(f,e[pre[i]].rest()); for (int i=t;i!=s;i=e[pre[i]].from) { e[pre[i]].flow+=f; e[pre[i]^1].flow-=f; Ans+=f*e[pre[i]].cost; } } bool spfa(int s,int t) { memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); memset(dis,inf,sizeof(dis)); queue<int> Q; Q.push(s); vis[s]=1,dis[s]=0; while (!Q.empty()) { int x=Q.front(); Q.pop(); for (int i=0;i<(int)G[x].size();i++) if (E.rest()&&dis[E.to]>dis[x]+E.cost) { dis[E.to]=dis[x]+E.cost; pre[E.to]=G[x][i]; if (!vis[E.to]) { vis[E.to]=1; Q.push(E.to); } } vis[x]=0; } return pre[t]!=-1; } void MiCMaF(int s,int t) { Ans=0; while (spfa(s,t)) updata(s,t); } #undef E int read() { int x=1; char ch; while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1; int s=ch-'0'; while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0'; return s*x; } int main() { n=read(),m=read(),k=read(); for (int i=1;i<=m;i++) { int x=read(),y=read(),z=read(),c=read(); add(x,y,z,0); X[i]=x,Y[i]=y,Z[i]=z,C[i]=c; } printf("%d ",Maxflow(1,n)); for (int i=1;i<=m;i++) add(X[i],Y[i],inf,C[i]); add(0,1,k,0); add(n,n+1,k,0); MiCMaF(0,n+1); printf("%d\n",Ans); return 0; }