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 wwlw @ 2020-03-22 19:16:16
@Lattle_Car 不会您就去学啊
by Laser_Crystal @ 2020-03-22 19:16:17
@TLE_er__psz orz……你怎么来了……别说出来……
by Laser_Crystal @ 2020-03-22 19:16:41
@wwlw 我这么蒟蒻学不会啊
by IntrepidStrayer @ 2020-03-22 19:17:38
@Lattle_Car 事实证明,不学就没有烦恼(像我,但是会比别人蒻)
by Yaixy @ 2020-03-22 21:19:30
萌新...妹子???