基于BFS的最大流算法(Edmonds)

#include<iostream>using namespace std;#define MAXN 10003bool Vis[100];int Map[100][100],F[100][100],n,Target,Min;struct queen{int top;int end;int node[100];}f;struct vertex{int back;bool dir;// if we enter x the dir would be 1, since leaving x,the dir would be 0.} Hase[100];bool BFS(int x){f.top=0;f.end=1;Vis[x]=1;f.node[f.top]=x;while(f.top!=f.end){int z=f.node[f.top];if(z==Target)return true;f.top=(f.top++)%50;for(int i=0;i<n;i++){if(F[z][i]<Map[z][i]&&Vis[i]==0){f.node[f.end]=i;f.end=(f.end++)%50;Vis[i]=1;Hase[i].back=z;Hase[i].dir=1;}if(F[i][z]>0&&Vis[i]==0){f.node[f.end]=i;f.end=(f.end++)%50;Vis[i]=1;Hase[i].back=z;Hase[i].dir=0;}}}return false;}void Solve(){int start;cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>Map[i][j];while(cin>>start>>Target){memset(Vis,0,sizeof(Vis));memset(Hase,-1,sizeof(Hase));memset(F,0,sizeof(F));while(BFS(start)){memset(Vis,0,sizeof(Vis));Min=MAXN;for(int i=Target;i!=start;i=Hase[i].back){if(Hase[i].dir==1)Min=min(Map[Hase[i].back][i] – F[Hase[i].back][i] , Min);elseMin=min(F[i][Hase[i].back] , Min);}for(int i=Target;i!=start;i=Hase[i].back){if(Hase[i].dir==1)F[Hase[i].back][i]+=Min;elseF[i][Hase[i].back]-=Min;}}for(int i=0;i<n;i++){for(int j=0;j<n;j++)cout<<F[i][j]<<" ";cout<<endl;}}}int main(){Solve();return 0;}

,真正的停下来,享受自我的体验时刻,也许浮光掠影,

基于BFS的最大流算法(Edmonds)

相关文章:

你感兴趣的文章:

标签云: