shyr @ 2023-01-13 07:41:25
/*Author:luogu uid 357163 shyr*/
#include<bits/stdc++.h>
#define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define Rof(i,a,b,c) for(int i=(b);i>=(a);i-=(c))
using namespace std;
typedef long long LL;
typedef double db;
#define int long long
typedef unsigned long long ULL;
template<typename t> t &read(t &x){
char c;int f=1;
while(!isdigit(c=getchar()))f=(c=='-')?-1:1;
x=c^'0';
while(isdigit(c=getchar()))x=x*10+(c^'0');
return x*=f;
}
int n,Nxt[205],m,s,t,u,v,w,cnt=1,nxt[205],dep[205];
LL ans;
struct node{
int a,b,c,lst;
void add(int A,int B,int C){
a=A,b=B,c=C,lst=nxt[a],nxt[a]=cnt;
}
}g[10001];
bool BFS(){
memset(dep,0,sizeof(dep));
dep[s]=1;queue<int>q;q.push(s);
while(q.size()){
int x=q.front();q.pop();Nxt[x]=nxt[x];
for(int i=nxt[x];i;i=g[i].lst){
int y=g[i].b;
if(g[i].c&&!dep[y]){
dep[y]=dep[x]+1;
q.push(y);
}
}
}
return dep[t];
}
LL DFS(int x,LL in){
if(x==t)return in;
LL out=0;
for(int i=Nxt[x];i&∈i=g[i].lst){
Nxt[x]=i;int y=g[i].b;LL val=g[i].c;
if(val&&dep[y]==dep[x]+1){
LL res=DFS(y,min(in,val));
g[i].c-=res,g[i^1].c+=res;
in-=res,out+=res;
}
}
if(!out)dep[x]=-1;
return out;
}
#define LOCAL
signed main(){
#ifdef LOCAL
freopen("P3376_8.in","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(n),read(m),read(s),read(t);
For(i,1,m,1){
read(u),read(v),read(w);
g[++cnt].add(u,v,w);
g[++cnt].add(v,u,0);
}
while(BFS())ans+=DFS(s,1e18);
printf("%lld\n",ans);
return 0;
}
下了数据#8本地跑的答案是 37381805875,和 out 一样。
但是显示 wrong answer On line 1 column 9, read 9, expected 8.
求问。
by shyr @ 2023-01-13 07:43:04
请忽略 #define LOCAL
,提交时显然注释了。
by Sunny郭 @ 2023-01-26 11:09:50
g数组开太小了,本地评测机好像不爆