分析&＃xff1a;第一个网络最大流的题目&＃xff0c;绝对经典&＃xff0c;值得一做。代码没怎么优化&＃xff0c;方便做参考。
Code
#include <iostream>#include <deque>#include <queue>using namespace std;#define MAXN 201int Map[MAXN][MAXN],n;typedef struct __Path
{
int s,t;
}Path; // 路typedef deque<Path> PathList; // 路径int CalMin(PathList path){ int min &＃61; 2000000000; for(PathList::iterator begin&＃61;path.begin();begin!&＃61;path.end();&＃43;&＃43;begin)
{ if(Map[begin->s][begin->t]<min) min &＃61; Map[begin->s][begin->t];
} return min;}bool FindPath(int &min,PathList &path,const int source,const int target){ bool used[MAXN][MAXN]; memset(used,0,sizeof(used)); queue<PathList> search_list; PathList t; Path p; p.s &＃61; source; t.push_back(p); search_list.push(t); while(!search_list.empty()) { t &＃61; search_list.front(); search_list.pop(); for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) { if(Map[t.back().s][i]>0 && !used[t.back().s][i]) { used[t.back().s][i] &＃61; true; PathList temp(t); temp.back().t &＃61; i; if(temp.back().t &＃61;&＃61; target) { min &＃61; CalMin(temp); path &＃61; temp; return true; } p.s &＃61; i; temp.push_back(p); search_list.push(temp); } } } return false;}int main(){ int m; while(cin>>m>>n) { memset(Map,0,sizeof(Map)); int s,e,c; for(int i&＃61;0;i<m;&＃43;&＃43;i) { cin>>s>>e>>c; Map[s][e] &＃43;&＃61; c; } int sum&＃61;0,min; PathList path; while(FindPath(min,path,1,n)) // 1为源点,n为汇点 { sum &＃43;&＃61; min; Path temp; while(!path.empty()) { temp &＃61; path.front(); path.pop_front(); Map[temp.s][temp.t] -&＃61; min; Map[temp.t][temp.s] &＃43;&＃61; min; } } cout<<sum<<endl; } return 0;}
京公网安备 11010802041100号