Dark_lightrq @ 2023-03-30 15:45:01
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=205,M=10005;
const LL INF=(1ll<<60)-1;
struct netflow{
int n,m,s,t;
int head[N],nxt[M],tot,ver[M];
LL w[M];
void add_(int x,int y,LL z){
ver[++tot]=y,nxt[tot]=head[x],head[x]=tot,w[tot]=z;
ver[++tot]=x,nxt[tot]=head[y],head[y]=tot,w[tot]=0;
}
int q[N],lev[N],cur[N];
bool bfs(){
for(int i=1;i<=n;i++){
lev[i]=0,cur[i]=head[i];
}
lev[s]=1;
int l,r;
q[l=r=1]=s;
while(l<=r){
int x=q[l++];
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(w[i]&&!lev[y]){
lev[y]=lev[x]+1;
q[++r]=y;
if(y==t)return 1;
}
}
}
return 0;
}
int dfs(int x,LL flow){
if(x==t)return flow;
LL res=0;
for(int &i=cur[x];i;i=nxt[i]){
int y=ver[i];
if(w[i]&&lev[y]==lev[x]+1){
int k=dfs(y,min(flow,w[i]));
flow-=k;
res+=k;
w[i]-=k;
w[i^1]+=k;
if(!flow)break;
}
}
if(!res)lev[x]=0;
return res;
}
LL dinic(){
LL ans=0;
while(bfs()){
ans+=dfs(s,INF);
}
return ans;
}
}T;
int main(){
T.tot=1;
scanf("%d%d%d%d",&T.n,&T.m,&T.s,&T.t);
for(int i=1;i<=T.m;i++){
int x,y;
LL z;
scanf("%d%d%lld",&x,&y,&z);
T.add_(x,y,z);
}
cout<<T.dinic();
return 0;
}
by Dark_lightrq @ 2023-03-30 15:53:19
WA了7,8,10
by AlicX @ 2023-03-30 16:02:42
在 Dinic 中你需要判断一下
by AlicX @ 2023-03-30 16:03:15
by Dark_lightrq @ 2023-03-30 16:07:34
@zhengdongwen 可是还是错了啊
by Dark_lightrq @ 2023-03-30 23:31:40
int dfs改为LL dfs就过了
by longlinyu7 @ 2024-06-23 19:46:55
@Dark_lightrq 好人一生平安,犯的错跟你一模一样