```cpp
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<cctype>
#include<stack>
#include<map>
#include<climits>
#include<set>
#include<iostream>
#define rint() read<int>()
#define rll() read<ll>()
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define gra(i,u) for(register int i=head[u];i;i=edge[i].nxt)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
inline int read()
{
register int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
return s*w;
}
const int INF=1e9;
const ll LLINF=1e18;
template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){int t=x;x=y;y=t;return;}
const int MAXN(1e3+10);
const int MAXM(15*MAXN);
int n,m,k;
struct E{int to,nxt,flow,cost;};
E edge[MAXN<<1];
int head[MAXN],tot(1);
inline void add(int u,int v,int f,int w)
{
edge[++tot].nxt=head[u];
head[u]=tot;
edge[tot].to=v;
edge[tot].flow=f;
edge[tot].cost=w;
return;
}
inline void add_edge(int u,int v,int f,int w)
{
add(u,v,f,w);
add(v,u,0,-w);
return;
}
queue<int>q;
int f[MAXN],d[MAXN],pre[MAXN],pos[MAXN];
bool inq[MAXN];
int s,t;
int nx[MAXN],ny[MAXN],c[MAXN],cap[MAXN];
inline bool spfa()
{
rep(i,s,t) d[i]=INF,f[i]=INF,inq[i]=false;
d[s]=0;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=false;
gra(i,u)
{
E e=edge[i];
if(e.flow&&d[e.to]>d[u]+e.cost)
{
d[e.to]=d[u]+e.cost;
f[e.to]=Min(f[u],e.flow);
pos[e.to]=i,pre[e.to]=u;
if(!inq[e.to]) inq[e.to]=true,q.push(e.to);
}
}
}
return f[s]!=f[t];
}
int mflow,mcost;
inline int MCMF()
{
mflow=0,mcost=0;
while(spfa())
{
mflow+=f[t];
mcost+=f[t]*d[t];
for(register int i=t;i!=s;i=pre[i])
{
int p=pos[i];
edge[p].flow-=f[t];
edge[p^1].flow+=f[t];
}
}
}
inline void remake()
{
Clear(head);
Clear(edge);
tot=1;
return;
}
int main()
{
n=read(),m=read(),k=read();
rep(i,1,m)
{
int u=read(),v=read(),f=read(),w=read();
add_edge(u,v,f,0);
nx[i]=u,ny[i]=v,cap[i]=f,c[i]=w;
}
s=1,t=n;
MCMF();
printf("%d ",mflow);
remake();
rep(i,1,m)
{
add_edge(nx[i],ny[i],cap[i],0);
add_edge(nx[i],ny[i],INF,c[i]);
}
t=n+1;
add_edge(n,t,mflow+k,0);
MCMF();
printf("%d\n",mcost);
return 0;
}
```
by UperFicial @ 2022-04-18 08:42:37
破案了,代码厌氧
by UperFicial @ 2022-04-18 09:20:22