Textbook_blasphemy @ 2021-05-16 16:37:35
#include<bits/stdc++.h>
using namespace std;
const long long inf=1<<29, N=3000010;
int head[N],d[N];
long long n, m, s, t, tot, max_flow;
queue<long long> q;
struct node{
long long to;
long long next;
long long dis;
}edge[N];
void add(long long x,long long y,long long z) {
edge[++tot].dis=y;
edge[tot].to=z;
edge[tot].next=head[x];
head[x]=tot;
edge[++tot].dis=x;
edge[tot].to=0;
edge[tot].next=head[y];
head[y]=tot;
}
long long bfs(){
memset(d,0,sizeof(d));
while(q.size())q.pop();
q.push(s);
d[s]=1;
while(q.size()){
long long x=q.front();
q.pop();
for(long long i=head[x];i;i=edge[i].next)
if(edge[i].to&&!d[edge[i].dis]){
q.push(edge[i].dis);
d[edge[i].dis]=d[x]+1;
if(edge[i].dis==t)return 1;
}
}
return 0;
}
long long dinic(long long x,long long flow){
if(x==t)return flow;
long long rest=flow,k;
for(long long i=head[x];i&&rest;i=edge[i].next)
if(edge[i].to&&d[edge[i].dis]==d[x]+1){
k=dinic(edge[i].dis,min(rest,edge[i].to));
if(!k)d[edge[i].dis]=0;
edge[i].to-=k;
edge[i^1].to+=k;
rest-=k;
}
return flow-rest;
}
int main(){
//freopen("P3376_7.txt","r",stdin);
scanf("%lld%lld",&n,&m);
scanf("%lld%lld",&s,&t);
tot=1;
for(long long i=1;i<=m;i++){
long long x,y,c;
scanf("%lld%lld%lld",&x,&y,&c);
add(x,y,c);
}
long long flow=0;
while(bfs())
while(flow=dinic(s,inf))max_flow+=flow;
printf("%lld",max_flow);
}
我下载了第七个测试点,不加文件读入RE(return 3221225477 w(゚Д゚)w)了,加了文件读入AC了(和out文件结果一样)
求答疑
by __ZXYAKIOI__ @ 2021-05-16 17:05:35
by RinkaSnow @ 2021-05-25 21:33:04
UB