1034. Head of a Gang (30)
考察搜索算法； 利用dfs或者bfs判断连通性，注意自己构造name和顶点的对应，本代码采用了map，通过name字符串快速查找对应顶点
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <map>using namespace std;struct answer{ string name; int num;};int visited[10000]={0};int cntp=0,maxt,head,sumtime;map<string,int> FName;vector<string> FIndex(10000);vector<vector<int>> v(10000);vector<int> rec;int timecnt[10000]={0};bool comp(const answer &a,const answer &b){ return a.name<b.name;}void DFS(int u){ if(visited[u]) return; visited[u]=1;cntp++;sumtime+=timecnt[u]; if(timecnt[u]>maxt) { maxt=timecnt[u]; head=u; } for(auto it=v[u].begin();it!=v[u].end();++it) DFS(*it);}int main(){ int n,limit,index=1; cin>>n>>limit; for(int i=0;i<n;++i) { string strl,strr; int time; cin>>strl>>strr>>time; if(!FName[strl]) { FName[strl]=index; FIndex[index]=strl; ++index; } if(!FName[strr]) { FName[strr]=index; FIndex[index]=strr; ++index; } int u=FName[strl],w=FName[strr]; v[u].push_back(w); v[w].push_back(u); rec.push_back(u); timecnt[u]+=time; timecnt[w]+=time; } vector<answer> ans; for(auto it=rec.begin();it!=rec.end();++it) { cntp=0;maxt=-1;head=-1;sumtime=0; DFS(*it); sumtime/=2; answer temp; if(maxt!=-1&&cntp>2&&sumtime>limit) { temp.name=FIndex[head]; temp.num=cntp; ans.push_back(temp); } } sort(ans.begin(),ans.end(),comp); cout<<ans.size()<<endl; for(auto it=ans.begin();it!=ans.end();++it) cout<<it->name<<" "<<it->num<<endl; return 0;}新闻热点
疑难解答
