求助大佬，这里bfs有问题

P3376 【模板】网络最大流

王奕霏 @ 2018-06-13 14:26:07

****72 C:\Users\Administrator\Desktop\main.cpp [Warning] the address of bool bfs()', will always evaluate astrue' 这个有毒啊 下面是代码，运行的时候输入完就会一直卡着了

include <iostream>

include <queue>

include <cstring>

using namespace std;

struct Node{ int from; int to; int capacity; int next; };

int heads[10010], target, sorce, level[10010], num_dian, num_bian; Node edges[200100];

int in(int from, int to, int capacity, int i){ edges[i].from=from; edges[i].to=to; edges[i].capacity=capacity; edges[i].next=heads[from]; heads[from]=i; edges[i+1].from=to; edges[i+1].to=from; edges[i+1].capacity=0; edges[i+1].next=heads[to]; heads[to]=i+1; }

bool bfs(){ queue<int> q; memset(level, -1, sizeof(level)); q.push(sorce); level[sorce]=0; while(!q.empty()){ int f=q.front(); if(f==target){ return true; } q.pop(); for(int i=heads[f];i!=-1;i=edges[i].next){ if(edges[i].capacity>0 && level[i]==-1){ q.push(i); level[i]=level[f]+1; } } } return false; }

int dfs(int from, int mx){ int ans=0; if(from==target || mx<=0){ return 0; } for(int i=heads[from];i!=-1;i=edges[i].next){ if(level[i]==level[from]+1 && edges[from].capacity>0){ int an=dfs(i, min(edges[i].capacity, mx-ans)); ans+=an; edges[i].capacity-=an; edges[i^1].capacity+=an; if(ans==mx){ return ans; } } } return ans; }

int dinic(){ int ans=0; while(bfs){ ans+=dfs(sorce, 0x3F3F3F3F); } return ans; }

int main(){ cin >> num_dian >> num_bian >> sorce >> target; memset(heads, -1, sizeof(heads)); for(int i=0;i<num_bian*2;i+=2){ int from, to, weight; cin >> from >> to >> weight; in(from, to, weight, i); } cout << dinic(); }

by 王奕霏 @ 2018-06-13 14:26:59

include <iostream>

include <queue>

include <cstring>

using namespace std;

struct Node{ int from; int to; int capacity; int next; };

int heads[10010], target, sorce, level[10010], num_dian, num_bian; Node edges[200100];

int in(int from, int to, int capacity, int i){ edges[i].from=from; edges[i].to=to; edges[i].capacity=capacity; edges[i].next=heads[from]; heads[from]=i; edges[i+1].from=to; edges[i+1].to=from; edges[i+1].capacity=0; edges[i+1].next=heads[to]; heads[to]=i+1; }

bool bfs(){ queue<int> q; memset(level, -1, sizeof(level)); q.push(sorce); level[sorce]=0; while(!q.empty()){ int f=q.front(); if(f==target){ return true; } q.pop(); for(int i=heads[f];i!=-1;i=edges[i].next){ if(edges[i].capacity>0 && level[i]==-1){ q.push(i); level[i]=level[f]+1; } } } return false; }

int dfs(int from, int mx){ int ans=0; if(from==target || mx<=0){ return 0; } for(int i=heads[from];i!=-1;i=edges[i].next){ if(level[i]==level[from]+1 && edges[from].capacity>0){ int an=dfs(i, min(edges[i].capacity, mx-ans)); ans+=an; edges[i].capacity-=an; edges[i^1].capacity+=an; if(ans==mx){ return ans; } } } return ans; }

int dinic(){ int ans=0; while(bfs){ ans+=dfs(sorce, 0x3F3F3F3F); } return ans; }

int main(){ cin >> num_dian >> num_bian >> sorce >> target; memset(heads, -1, sizeof(heads)); for(int i=0;i<num_bian*2;i+=2){ int from, to, weight; cin >> from >> to >> weight; in(from, to, weight, i); } cout << dinic(); }

by 王奕霏 @ 2018-06-13 14:28:50

bool bfs(){

queue<int> q;

memset(level, -1, sizeof(level));

q.push(sorce);

level[sorce]=0;

while(!q.empty()){

int f=q.front();

if(f==target){

return true;

}

q.pop();

for(int i=heads[f];i!=-1;i=edges[i].next){

if(edges[i].capacity>0 && level[i]==-1){

q.push(i);

level[i]=level[f]+1;

}

}

}

return false;

}

by moye到碗里来 @ 2018-06-13 15:00:47

bool bfs(){

queue<int> q;

memset(level, -1, sizeof(level));

q.push(sorce);

level[sorce]=0;

while(!q.empty()){

int f=q.front();

if(f==target){

return true;

}

q.pop();

for(int i=heads[f];i!=-1;i=edges[i].next){

if(edges[i].capacity>0 && level[i]==-1){

q.push(i);

level[i]=level[f]+1;
}

}

}

return false;

}
//有毒把。。

by moye到碗里来 @ 2018-06-13 15:01:19

用markdown a

by 王奕霏 @ 2018-06-13 15:34:25

恩恩谢！！

by 王奕霏 @ 2018-06-13 15:36:07

#include <iostream> 
#include <queue>
#include <cstring>

using namespace std;

struct Node{
 int from;
 int to;
 int capacity;
 int next;
};

int heads[10010], target, sorce, level[10010], num_dian, num_bian;
Node edges[200100];

int in(int from, int to, int capacity, int i){
  edges[i].from=from;
  edges[i].to=to;
  edges[i].capacity=capacity;
  edges[i].next=heads[from];
  heads[from]=i;
  edges[i+1].from=to;
  edges[i+1].to=from;
  edges[i+1].capacity=0;
  edges[i+1].next=heads[to];
  heads[to]=i+1;
}

bool bfs(){
 cout << "a1";
 queue<int> q;
 memset(level, -1, sizeof(level));
 q.push(sorce);
 level[sorce]=0;
 while(!q.empty()){
  int f=q.front();
  if(f==target){
   cout << "true" << endl;
   return true;
  }
  cout << "a" << endl;
  q.pop();
  for(int i=heads[f];i!=-1;i=edges[i].next){
   if(edges[i].capacity>0 && level[i]==-1){
    q.push(i);
    level[i]=level[f]+1;
   }
  }
 }
 return false;
}

int dfs(int from, int mx){
 int ans=0;
 if(from==target || mx<=0){
  return 0;
 }
 for(int i=heads[from];i!=-1;i=edges[i].next){
  if(level[i]==level[from]+1 && edges[from].capacity>0){
   int an=dfs(i, min(edges[i].capacity, mx-ans));
   ans+=an;
   edges[i].capacity-=an;
   edges[i^1].capacity+=an;
   if(ans==mx){
    return ans;
   }
  }
 }
 return ans;
}

int dinic(){
 int ans=0;
 cout << "b";
 while(bfs){
  cout << "a2";
  ans+=dfs(sorce, 0x3F3F3F3F);
 }
 return ans;
}

int main(){
 cin >> num_dian >> num_bian >> sorce >> target;
 memset(heads, -1, sizeof(heads));
 for(int i=0;i<num_bian*2;i+=2){
  int from, to, weight;
  cin >> from >> to >> weight;
  in(from, to, weight, i);
 }
 cout << dinic();
}

by 王奕霏 @ 2018-06-13 15:36:21

哪位大佬看看

by info___tion @ 2018-07-06 09:40:57

@王奕霏 你这bfs并不是十分清晰啊……

我的bfs是这样的（感觉自己的清晰了不少）

bool bfs()
{
    memset(vis,false,sizeof(vis));

    queue<int>Q;
    Q.push(s);

    dis[s]=0,vis[s]=true;

    while(!Q.empty())
    {
        int head=Q.front();
        Q.pop();

        for(int i=0;i<G[head].size();i++)
        {
            node& e=E[G[head][i]];

            if( !vis[e.to] && e.cap>e.flow )
            {
                vis[e.to]=true;
                dis[e.to]=dis[head]+1;

                Q.push(e.to);
            }
        }
    }

    return vis[t];
}

by info___tion @ 2018-07-06 09:42:54

@王奕霏 诶，好像看出来了，你的bfs在加入节点的时候为什么只是\color{blue}push(i)呢？（不是应该\color{blue}push(i.to) 吗？）

by info___tion @ 2018-07-06 09:44:37

@王奕霏 你只\color{blue}push(i)的话不死循环才怪（反正来来去去都是同一条边）

|