sycqwq @ 2021-05-30 15:54:35
rt
下了数据输出是对的
就是re
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1ll<<63;
int n,m,s,t;
struct node
{
int v,w,nxt;
}e[100005];
int tot=1;
int head[100005];
int add(int u,int v,int w)
{
e[++tot].v=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
int mi[10005],q[10005],bk[10005];
int bfs()
{
memset(bk,0,sizeof bk);
queue<int> qq;
qq.push(s);
bk[s]=1;
mi[t]=inf;
while(!qq.empty())
{
// cout<<1<<endl;
int x=qq.front();
qq.pop();
for(int i=head[x];i;i=e[i].nxt)
{
if(e[i].w<=0)
continue;
if(bk[e[i].v])
continue;
mi[e[i].v]=min(e[i].w,x);
q[e[i].v]=i;
if(e[i].v==t)
return 1;
bk[e[i].v]=1;
qq.push(e[i].v);
}
}
return 0;
}
signed main(){
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
int x,y,w;
cin>>x>>y>>w;
add(x,y,w);
add(y,x,0);
}
int ans=0;
while(1)
{
// cout<<1<<endl;
if(!bfs())
break;
int x=t;
while(x!=s)
{
int v=q[x];
e[v].w-=mi[t];
e[v^1].w+=mi[t];
x=e[v^1].v;
// getchar();
}
// cout<<"###############"<<endl;
ans+=mi[t];
}
cout<<ans;
return 0;
}
by cunzai_zsy0531 @ 2021-05-30 16:41:51
你可以试试把某个函数注释掉,先搞清楚RE原因
by Shymeleaf @ 2022-11-27 23:22:13
请问您问题解决了吗?