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 Laser_Crystal @ 2020-03-22 19:05:44
@TeddyWang 边看珂朵莉边学的
by IntrepidStrayer @ 2020-03-22 19:07:14
实义动词才能用do提问。。。
by IntrepidStrayer @ 2020-03-22 19:08:00
@TeddyWang You确实要补一补英语。。。
by NatHedRoll @ 2020-03-22 19:09:22
必须要奖项认证
by dingcx @ 2020-03-22 19:09:32
qndmxmz
by Scherzo @ 2020-03-22 19:10:25
萌新刚学网络流
这哪是人话啊,装弱,举报了(大雾)
by wwlw @ 2020-03-22 19:13:53
Dinic它不香吗
by Laser_Crystal @ 2020-03-22 19:14:06
@wwlw 窝不会
by Loser_King @ 2020-03-22 19:14:36
@Lattle_Car btd,jbl(你明明就是male!
by Ryo_Yamada @ 2020-03-22 19:15:39
@Lattle_Car @fhh_orz
他这是学JCodingenglish men说话……
玩梗,jbl