@[zhy_learn](/user/327567) 您可以看看我去年暑假的时候在这题讨论区发的帖子。
by zimujun @ 2022-03-13 16:08:07
https://www.luogu.com.cn/discuss/342965
by zimujun @ 2022-03-13 16:12:36
@[zimujun](/user/118196) 变成WA60了
by zhy_learn @ 2022-03-13 16:48:10
@[zimujun](/user/118196)
```cpp
#include<bits/stdc++.h>
#define Fu(i,a,b) for(register int i=(a);i<=(b);i++)
#define Fd(i,a,b) for(register int i=(a);i>=(b);i--)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
int n,m,s,t,fi[50005],cur[50005],mf,mc,cnt=1;
struct edge{
int ne,to,f,w;
}e[1000005];
void add(int u,int v,int w,int f){
e[++cnt].to=v,e[cnt].ne=fi[u],e[cnt].w=w,e[cnt].f=f,fi[u]=cnt;
e[++cnt].to=u,e[cnt].ne=fi[v],e[cnt].w=0,e[cnt].f=-f,fi[v]=cnt;
}
int q[1000005],bj[50005],dis[50005],flow[50005],p[50005],l,r;
bool SPFA(){
l=0,r=1;
memset(bj,0,sizeof(bj));
memset(dis,127/3,sizeof(dis));
Fu(i,0,n) cur[i]=fi[i];
flow[s]=0x7fffffff,q[1]=s,bj[s]=1,dis[s]=0;
while(l<r){
int u=q[++l];
bj[u]=0;
for(int i=fi[u];i;i=e[i].ne){
int v=e[i].to;
if(e[i].w&&dis[u]+e[i].f<dis[v]){
dis[v]=dis[u]+e[i].f;
if(!bj[v]) q[++r]=v,bj[v]=1;
}
}
}
return dis[t]!=dis[0];
}
int dfs(int u,int in){
if(u==t||in==0) return in;
int out=0;
for(int &i=cur[u];i;i=e[i].ne){
int v=e[i].to;
if(!bj[v]&&e[i].w&&dis[v]==dis[u]+e[i].f){
bj[v]=1;
int o=dfs(v,min(in,e[i].w));
bj[v]=0;
e[i].w-=o;
e[i^1].w+=o;
in-=o,out+=o;
mc+=o*e[i].f;
if(in==0) break;
}
}
if(out==0) dis[u]=-1;
return out;
}
void MCMF(){
while(SPFA()) mf+=dfs(s,0x7fffffff);
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
Fu(i,1,m){
int u,v,w,f;
scanf("%d%d%d%d",&u,&v,&w,&f);
add(u,v,w,f);
}
MCMF();
printf("%d %d",mf,mc);
return 0;
}
```
这样吗???
by zhy_learn @ 2022-03-13 16:49:34