打破0回复
by tangrunxi @ 2020-03-18 09:50:32
```
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define _min(x,y) ((x)<(y)?(x):(y))
#define INF 0x7f
inline int read(){
register int x=0,f=0,ch=getchar();
while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
return f?-x:x;
}
queue<int>q;
const int MAX=50005;
int u,v,w,p,n,m,S,T;
struct E{
int e,next,w,p;
}e[MAX<<1];
int head[MAX],cnt=2;
inline void add(int u,int v,int w,int p){
e[cnt]=(E){v,head[u],w,p};head[u]=cnt++;
e[cnt]=(E){u,head[v],0,-p};head[v]=cnt++;
}
int x,vis[MAX],flow[MAX],dis[MAX],pre[MAX],pr[MAX];
int ans,d;
inline bool spfa(int s,int t){
while(!q.empty())q.pop();
memset(dis,INF,sizeof(dis));
memset(flow,INF,sizeof(flow));
dis[s]=0;q.push(s);pre[t]=0;vis[s]=1;
while(!q.empty()){
x=q.front();q.pop();
vis[x]=0;
for(register int i=head[x];i;i=e[i].next){
if(e[i].w&&dis[e[i].e]>dis[x]+e[i].p){
dis[e[i].e]=dis[x]+e[i].p;
flow[e[i].e]=_min(flow[x],e[i].w);
pre[e[i].e]=x;pr[e[i].e]=i;
if(!vis[e[i].e]){
vis[e[i].e]=1;
q.push(e[i].e);
}
}
}
}
return pre[t];
}
inline void eK(int s,int t){
while(spfa(s,t)){
ans+=flow[t];x=t;
d+=flow[t]*dis[t];
while(x!=s){
e[pr[x]].w-=flow[t];
e[pr[x]^1].w+=flow[t];
x=pre[x];
}
}
}
signed main(){
// freopen("P3381_8.in","r",stdin);
n=read(),m=read(),S=read(),T=read();
for(register int i=1;i<=m;++i){
u=read(),v=read(),w=read(),p=read();
add(u,v,w,p);
}
eK(S,T);
printf("%d %d\n",ans,d);
return 0;
}
```
by zsaskk @ 2020-03-18 09:58:55
@[Lates](/user/119062)
by zsaskk @ 2020-03-18 09:59:00
@[zsaskk](/user/134640) 谢谢
by Lates @ 2020-03-18 10:04:01