首页 > 代码库 > PAT-1034 Head of a Gang (30)
PAT-1034 Head of a Gang (30)
这道题目刚开始想用并查集来做，但是其实不通的，因为有可能是环，不确保是一个图。
这道题目第一想法应该是用DFS来做，BFS也行，不过用DFS习惯了。
// 1034.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include<stdio.h>#include<string.h>#include<string>//string 使用c++的string，如果使用c语言的string，那么就会导致map声明时候的问题，所以加载时候最好使用string; using namespace std;#include<map>#include<vector>#include<algorithm>using namespace std;map<string,int> dir;map<int,string> dir2;struct Pair{ Pair(int d,int n) { data=d; next=n; } int data; int next;};vector<Pair> v;vector<int> tmp;bool visited[2010][2010];bool nodev[2010];int m[2010][2010];int weight[2010];int size;int max_index=-1,Max=-1,sum=0,num=0;//最大是谁，和是多少，有多少个人int findIndex(string str){ map<string,int>::iterator it=dir.find(str); if(it!=dir.end()) return it->second; else { dir.insert(make_pair(str,dir.size()+1)); dir2.insert(make_pair(dir2.size()+1,str)); return dir.size(); }}string findString(int index){ map<int,string>::iterator it=dir2.find(index); /*for(it=dir.begin();it!=dir.end();it++) { if(it->second==index) { ret=it->first; break; } }*/ return it->second;}bool cmp(Pair a,Pair b){ if(findString(a.data)<findString(b.data)) { return true; } return false;}void dfs(int index){ nodev[index]=true; if(find(tmp.begin(),tmp.end(),index)==tmp.end()) { tmp.push_back(index); } for(int i=1;i<=size;i++) { if(i==index) continue; if(!visited[i][index]&&m[i][index]!=0) { sum=sum+m[i][index]; weight[i]+=m[i][index]; weight[index]+=m[i][index]; if(weight[i]>Max) { Max=weight[i]; max_index=i; } if(weight[index]>Max) { Max=weight[index]; max_index=index; } if(find(tmp.begin(),tmp.end(),i)==tmp.end()) { tmp.push_back(i); } visited[i][index]=visited[index][i]=true; dfs(i); } }}int main(){ int n,k; int t; int index1,index2; freopen("1034-in.txt","r",stdin); char a[20]; char b[20]; while(scanf("%d%d",&n,&k)!=EOF) { memset(m,0,sizeof(int)*2010*2010); memset(visited,0,sizeof(bool)*2010*2010); memset(weight,0,sizeof(int)*2010); memset(nodev,0,sizeof(int)*2010); for(int i=1;i<=n;i++) { scanf("%s%s%d",a,b,&t); index1=findIndex(string(a));//string char c style index2=findIndex(string(b)); if(m[index1][index2]!=0) { m[index1][index2]=m[index2][index1]=m[index1][index2]+t; } else { m[index1][index2]=m[index2][index1]=t; } } //search size=dir.size(); while(true) { int unvis=-1; for(int i=1;i<=size;i++) { if(!nodev[i]) { unvis=i; break; } } if(unvis==-1) break; dfs(unvis); if(sum>k&&tmp.size()>=3) v.push_back(Pair(max_index,tmp.size())); tmp.clear(); max_index=-1,Max=-1,sum=0,num=0; } int count=v.size(); printf("%d\n",count); sort(v.begin(),v.end(),cmp); for(int i=0;i<count;i++) { printf("%s %d\n",findString(v[i].data).c_str(),v[i].next); } } return 0;}
1）在用字符串做索引的时候，我喜欢用map来查找对应的索引值，这样效率很高，logn的算法。这道题目有从string到index的索引，有从index到string的索引。刚开始建立的是从string到index的索引，这样从index到string索引时候，我是采用遍历的方式来比对string的。这样导致了最后一个case超时，但是大部分时候内存是不会超过限制的，用内存换时间是很合得来的。所以我又建立了一个以index为索引，值为string的索引。这样最后一个测试用例就过去了。
2） 这道题目dfs遍历的是边，而不是顶点，当然还是以顶点作为切入。这不是一个树或者图，这是一个有可能不连通的有环图。
3）dfs时候需要返回多个值，直接以全局变量放进去了，每次遍历完一片区域就清空。
注意：
这道题目描述的是变数不超过1000,加入1000条边都是不相连的，那么就会有2000个顶点。有一个测试用例顶点数目很多。
PAT-1034 Head of a Gang (30)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。