对于第一问，直接求最大流。
对于第二问，建源点s和汇点t，s连1容量为INF,费用为0的边，n连t容量为最大流+k，费用为0的边。这样就把最大流限制为最多增加k了。
限制需要求扩充的最小费用，原图的边多连一条容量为INF,费用为增容费用K的边。跑一遍费用流即是答案。
# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi 3.1415926535 # define eps 1e-9 # define MOD 1000000009 # define INF 1000000000 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; int Scan() { int res=0, flag=0; char ch; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch-'0'); return flag?-res:res; } void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0'); } const int N=1005; //Code begin... struct Edge{int p, next, w;}edge[N*10]; struct Edge1{int to, next, cap, flow, cost;}edge1[N*20]; struct Node{int u, v, C, K;}node[5005]; int head[N], cnt=2, s, t; int vis[N], head1[N], tol, pre[N], dis[N]; bool mark[N]; queue<int>Q; void add_edge(int u, int v, int w){ edge[cnt].p=v; edge[cnt].next=head[u]; edge[cnt].w=w; head[u]=cnt++; edge[cnt].p=u; edge[cnt].next=head[v]; edge[cnt].w=0; head[v]=cnt++; } void addedge(int u, int v, int cap, int cost){ edge1[tol].to=v; edge1[tol].cap=cap; edge1[tol].cost=cost; edge1[tol].flow=0; edge1[tol].next=head1[u]; head1[u]=tol++; edge1[tol].to=u; edge1[tol].cap=0; edge1[tol].cost=-cost; edge1[tol].flow=0; edge1[tol].next=head1[v]; head1[v]=tol++; } bool spfa(int s, int t){ FOR(i,s,t) dis[i]=INF, mark[i]=false, pre[i]=-1; dis[s]=0; mark[s]=true; Q.push(s); while (!Q.empty()) { int u=Q.front(); Q.pop(); mark[u]=false; for (int i=head1[u]; i!=-1; i=edge1[i].next) { int v=edge1[i].to; if (edge1[i].cap>edge1[i].flow&&dis[v]>dis[u]+edge1[i].cost) { dis[v]=dis[u]+edge1[i].cost; pre[v]=i; if (!mark[v]) mark[v]=true, Q.push(v); } } } if (pre[t]==-1) return false; else return true; } int minCostMaxflow(int s, int t, int &cost){ int flow=0; cost=0; while (spfa(s,t)) { int Min=INF; for (int i=pre[t]; i!=-1; i=pre[edge1[i^1].to]) { Min=min(Min,edge1[i].cap-edge1[i].flow); } for (int i=pre[t]; i!=-1; i=pre[edge1[i^1].to]) { edge1[i].flow+=Min; edge1[i^1].flow-=Min; cost+=edge1[i].cost*Min; } flow+=Min; } return flow; } int bfs(){ int i, v; mem(vis,-1); vis[s]=0; Q.push(s); while (!Q.empty()) { v=Q.front(); Q.pop(); for (i=head[v]; i; i=edge[i].next) { if (edge[i].w>0 && vis[edge[i].p]==-1) { vis[edge[i].p]=vis[v] + 1; Q.push(edge[i].p); } } } return vis[t]!=-1; } int dfs(int x, int low){ int i, a, temp=low; if (x==t) return low; for (i=head[x]; i; i=edge[i].next) { if (edge[i].w>0 && vis[edge[i].p]==vis[x]+1){ a=dfs(edge[i].p,min(edge[i].w,temp)); temp-=a; edge[i].w-=a; edge[i^1].w += a; if (temp==0) break; } } if (temp==low) vis[x]=-1; return low-temp; } int main () { int n, m, k, ans; mem(head1,-1); scanf("%d%d%d",&n,&m,&k); s=0; t=n+1; add_edge(s,1,INF); add_edge(n,t,INF); FOR(i,1,m) { scanf("%d%d%d%d",&node[i].u,&node[i].v,&node[i].C,&node[i].K); add_edge(node[i].u,node[i].v,node[i].C); } int tmp, sum=0; while (bfs()) while (tmp=dfs(s,INF)) sum+=tmp; addedge(s,1,INF,0); addedge(n,t,sum+k,0); FOR(i,1,m) { addedge(node[i].u,node[i].v,node[i].C,0); addedge(node[i].u,node[i].v,INF,node[i].K); } minCostMaxflow(s,t,ans); printf("%d %d ",sum,ans); return 0; }