暗影之梦 @ 2022-03-18 18:32:07
#include<iostream>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
putchar(x%10+'0');
return;
}
putchar(x+'0');
}
int n,m,s,t,head[100001],cnt,dep[2001],nwb[2001];
struct edge1
{
int to,nxt,w;
}e[100001];
void edge(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int dfs(int nw,int w)
{
if(nw==t||w==0) return w;
for(int &i=nwb[nw];i;i=e[i].nxt)
{
if(dep[e[i].to]==dep[nw]+1&&e[i].w);
{
int wi=dfs(e[i].to,min(w,e[i].w));
if(wi>0)
{
e[i].w-=wi;
e[i^1].w+=wi;
return wi;
}
}
}
return 0;
}
int bfs()
{
queue<int> q;
memset(dep,-1,sizeof(dep));
dep[s]=1;
q.push(s);
while(!q.empty())
{
int nw=q.front();
q.pop();
for(int i=head[nw];i;i=e[i].nxt)
{
if(e[i].w&&dep[e[i].to]==-1)
{
dep[e[i].to]=dep[nw]+1;
q.push(e[i].to);
if(e[i].to==t) return 1;
}
}
}
return 0;
}
int dinic()
{
int ans=0;
while(bfs())
{
// cout<<114514<<endl;
for(int i=1;i<=n;i++) nwb[i]=head[i];
while(int ans1=dfs(s,1e16)) ans+=ans1;
}
return ans;
}
signed main()
{
n=read(),m=read(),s=read(),t=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
edge(u,v,w);
edge(v,u,0);
}
write(dinic());
return 0;
}
dfs和bfs出了问题但找不到,求大佬们帮忙看看
by 暗影之梦 @ 2022-03-19 11:41:08
已经A了,本帖终结