1034. Head of a Gang (30)

发布时间:2014-10-23 23:29:09
来源:分享查询网

1034. Head of a Gang (30) #include <iostream> #include <string> #include <vector> #include <map> using namespace std; class CA { public: void run(); void addmap(string &s1,string &s2,int w); vector<map<string,int> > culist; vector<int> wlist; int n,k; }; void CA::addmap(string &s1,string &s2,int w) { int i,m1=-1,m2=-1; map<string,int>::iterator im; for(i=0;i<culist.size();i++) { im=culist[i].find(s1); if(im!=culist[i].end()) { m1=i; break; } } for(i=0;i<culist.size();i++) { im=culist[i].find(s2); if(im!=culist[i].end()) { m2=i; break; } } if(m1==-1&&m2==-1) { map<string,int> mp; mp[s1]=w;mp[s2]=w; culist.push_back(mp); wlist.push_back(w); } else if(m1==-1&&m2!=-1) { culist[m2][s1]=w; culist[m2][s2]+=w; wlist[m2]+=2; } else if(m1!=-1&&m2==-1) { culist[m1][s1]+=w; culist[m1][s2]=w; wlist[m1]+=w; } else if(m1!=-1&&m2!=-1&&m1==m2) { culist[m1][s1]+=w; culist[m1][s2]+=w; wlist[m1]+=w; } else if(m1!=-1&&m2!=-1&&m1!=m2) { culist[m1][s1]+=w; culist[m2][s2]+=w; wlist[m1]+=w; for(im=culist[m2].begin();im!=culist[m2].end();++im) { culist[m1][im->first]=im->second; } culist.erase(culist.begin()+m2); wlist.erase(wlist.begin()+m2); } } void CA::run() { cin>>n>>k; string s1,s2; int w,i; map<string,int>::iterator im,immax; map<string,int> glist; while(n-->0) { cin>>s1>>s2>>w; addmap(s1,s2,w); } for(i=0;i<culist.size();i++) { if(culist[i].size()<=2) continue; if(wlist[i]<=k) continue; immax =culist[i].begin(); for(im=immax,++im;im!=culist[i].end();++im) { if(immax->second<im->second) immax=im; } // cout<<immax->first<<" "<<immax->second<<endl; glist[immax->first]=culist[i].size(); } if(glist.size()>0) { cout<<glist.size()<<endl; for(im=glist.begin();im!=glist.end();++im) { cout<<im->first<<" "<<im->second<<endl; } } else { cout<<0; } } int main() { // freopen("test.in","r",stdin); CA *a=new CA; a->run(); return 0; }

返回顶部
查看电脑版