萌新妹子,刚学网络流,问个问题

P3376 【模板】网络最大流

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

萌新...妹子???


上一页 |