Laser_Crystal @ 2020-03-22 19:02:44
#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
int n,m,s,t;
struct node
{
int to,w,next;
} e[MAXN];
int cnt=0;
int head[MAXN];
void addedge(int from,int to,int w)
{
cnt++;
e[cnt].next=head[from];
e[cnt].to=to;
e[cnt].w=w;
head[from]=cnt;
cnt++;
e[cnt].next=head[to];
e[cnt].to=from;
e[cnt].w=0;
head[to]=cnt;
}
int answer=0;
queue <int> q;
int fa[MAXN],v[MAXN];
void clear()
{
queue <int> empty;
while(!empty.empty()) empty.pop();
swap(empty,q);
}
int pr[MAXN];
int bfs(int s,int t)
{
clear();
memset(fa,-1,sizeof(fa));
fa[s]=0;
q.push(s);
v[s]=0x3f3f3f3f3f;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x]; i; i=e[i].next)
{
if(fa[e[i].to]==-1&&e[i].w>0)
{
v[e[i].to]=min(e[i].w,v[x]);
fa[e[i].to]=x;
pr[e[i].to]=i;
q.push(e[i].to);
}
}
}
if(fa[t]==-1) return -1;
else return v[t];
}
void EK(int s,int t)
{
int kk=0;
while(bfs(s,t)!=-1)
{
int k=t;
kk=bfs(s,t);
while(k!=s)
{
e[pr[k]].w-=kk;
e[pr[k]+1].w+=kk;
k=fa[k];
}
answer+=kk;
}
cout<<answer;
}
int main ()
{
cin>>n>>m>>s>>t;
for(int i=1; i<=m; i++)
{
int front,to,w;
cin>>front>>to>>w;
addedge(front,to,w);
}
EK(s,t);
return 0;
}
就是上面是我的代码,但是后来看到大佬们的代码,就发现bfs里总是有这么一句话:
if(x==t) break;//因为找到一个就够了
这句话去掉的话居然不会TLE或者WA?(看着我这个很可能被卡掉的代码交上去崩的一下AC了我心里百感交集(可能是我蒟蒻过头罢))
by Implicit @ 2020-03-22 19:03:23
多找几个多好啊
by WangSQ0818Teddy @ 2020-03-22 19:03:38
@Lattle_Car
by DeepSkyBlue__ @ 2020-03-22 19:03:58
btd
by Laser_Crystal @ 2020-03-22 19:04:06
@TeddyWang 不应该是are you sure吗
by Smile_Cindy @ 2020-03-22 19:04:13
@Lattle_Car 不会,因为EK的bfs本身就需要
by Smile_Cindy @ 2020-03-22 19:04:33
@TeddyWang 您的英语需要补习。
by Laser_Crystal @ 2020-03-22 19:04:34
@Alpha 谢谢
by WangSQ0818Teddy @ 2020-03-22 19:05:07
@Lattle_Car 嗯?你英语怎么学的?
by Karrγ5307 @ 2020-03-22 19:05:16
qndmx!
by IntrepidStrayer @ 2020-03-22 19:05:42
@TeddyWang sure在这里是形容词。。。