- #include<iostream>
- #include<map>
- #include<set>
- #include<vector>
- // 研究一下 stringToInt
- using namespace std;
- map<string,int>stringToInt;
- map<string,int>time1;
- set<string>s;
- map<int,string>IntTostring;
- const int MAXV=1010;
- bool G[MAXV][MAXV]={false};
- int weight[MAXV][MAXV],we[MAXV]={0},count=0,tot=0,aut=0,head,max1,tot1=0,maxv;
- bool visited[MAXV];
- vector<int>v1;
- vector<int>v2;
- int reverse(string s){
- if(stringToInt[s]==0){
- stringToInt[s]=++aut;
- IntTostring[aut]=s;
- maxv=aut;
- return aut;
- }else return stringToInt[s];
- }
- int DFS(int v){
- count++;
- visited[v]=true;
- for(int i=1;i<MAXV;i++){
- if(weight[v][i]!=0&&!G[v][i]){
- tot+=weight[v][i];
- G[v][i]=true;
- if(we[i]>max1){
- max1=we[i];
- head=i;
- }
- if(!visited[i])
- DFS(i);
- }
- }
- return head;
- }
- int main(){
- int n,sx,w;
- string name1,name2;
- cin>>n>>sx;
- for(int i=0;i<n;i++){
- cin>>name1>>name2>>w;
- int n1=reverse(name1);
- int n2=reverse(name2);// 转成数字
- we[n1]+=w;
- we[n2]+=w;
- weight[n1][n2]=w;
- }
- for(int i=1;i<MAXV;i++){
- if(!visited[i]){
- count=0;
- tot=0;
- tot1++;
- max1=we[i];
- head=i;
- int head=DFS(i);
- if(tot>sx&&count>2){
- // v1.push_back(head);
- // v2.push_back(count);
- time1[IntTostring[head]]=count;
- s.insert(IntTostring[head]);
- }
- }
- }
- cout<<s.size()<<endl;
- for(auto it=s.begin();it!=s.end();it++){
- cout<<*it<<" "<<time1[*it]<<endl;
- }
- return 0;
- }
这个代码的第三个测试点因为段错误而错误, 但是始终找不到错误点, 猜测和数组越界无关而和递归溢出有关
-----------------------------------------------------------------------------------------------
在实现字符串对数的映射时可以使用:
- int reverse(string s){
- if(stringToInt[s]==0){
- stringToInt[s]=++aut;
- IntTostring[aut]=s;
- maxv=aut;
- cout<<"---------------"<<s<<"对应"<<aut<<endl;
- return aut;
- }else return stringToInt[s];
- }
另外我发现在 pat 上能跑出来的代码. 上传到牛客网上最多只能对一半 让人心慌
A1034
来源: http://www.bubuko.com/infodetail-3399731.html