PAT 1003 Universal Travel Sites

PAT 1003 Universal Travel Sites

第一次尝试做顶级的试题,虽说代码还有很多不成熟的地方但能够做出来还是挺高兴的.

考察的是最大流问题

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <stack>
#include <climits>
#include <cstring>
struct AdjVer{int id;int weight;bool hasdelete=false;
};
using namespace std;
int N;
map<string,int> strToInt;
map<int,string> intToStr;
map<int,vector<AdjVer*>> graph;
vector<int> path;
bool flag;
void dfs(int x,int dest, bool* visited){visited[x]= true;path.push_back(x);if (x==dest){flag= true;return;} else{for (auto & i : graph[x]) {int a=i->id;if (!visited[a] && !i->hasdelete){dfs(a,dest,visited);if (flag){//发现了路径,那么就可以反悔了,不需要弹出return;}}}path.pop_back();}
}
int findMaxFlow(int src,int dest){bool visited[N];int sum=0;do{memset(visited, false, sizeof(visited));flag= false;path.clear();dfs(src,dest,visited);vector<int > vector1(path);
//        int size=path.size();//debug时使用,观察path长度if (!flag){break;//没有找到路径}int min_Val=INT_MAX;for (int i = 0; i < path.size()-1; ++i) {int a=path[i];int b=path[i+1];AdjVer *adjVer = nullptr;for(auto x:graph[a]){if (x->id==b){adjVer=x;break;}}min_Val=min(min_Val,adjVer->weight);}//找到最小值sum+=min_Val;for (int i = 0; i < path.size()-1; ++i) {int a=path[i];int b=path[i+1];for (auto x:graph[a]){if (x->id==b){x->weight-=min_Val;if(x->weight==0){x->hasdelete= true;}break;}}//对路径还需要进行增广操作,也就是反向边增加bool hasfind= false;for(auto x:graph[b]){if (x->id==a){x->weight+=min_Val;hasfind= true;}}if (!hasfind){//增加一条边auto* adj=new AdjVer();adj->id=a;adj->weight=min_Val;graph[b].push_back(adj);}}}while (true);return sum;
}int main() {string source,dest;cin>>source>>dest;cin>>N;strToInt[source]=0;intToStr[0]=source;strToInt[dest]=1;intToStr[1]=dest;int id=2;for (int i = 0; i < N; ++i) {string a,b;int val;cin>>a>>b;cin>>val;if (strToInt.find(a)=&#d()){strToInt[a]=id;intToStr[id]=a;id++;}if (strToInt.find(b)=&#d()){strToInt[b]=id;intToStr[id]=b;id++;}auto* adjVer=new AdjVer();adjVer->id=strToInt[b];adjVer->weight=val;graph[strToInt[a]].push_back(adjVer);}cout<<findMaxFlow(0,1)<<endl;return 0;
}