PAT A1034 并查集或者使用DFS图都可以
题目给定一群人沟通时长，有沟通过的全部算成一组（a和b打，b和c打，a和c一族的），看有几个组大于俩人且权值大于k
首先：并查集
几个需要注意的点
1、输出结果需要是按照字母顺序排序的
2、这个来回都是1000，那么开数组要开到两千，包括father的初始，踩坑了
3、string还是用cin和cout，scanf读出来的在后面会出现奇怪的问题（另外map只能用string不能用char a[]）
4、Union的过程加上对weight的判断
5、注意最后输出的是组内人数
6、判断k的是整个组的沟通，个人weight叠加以后需要/2的
7、mp.find(x)返回的是迭代器，要用mp[str]才是数字
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<map> #include<algorithm> using namespace std; map<string,int>mp; int father[2005]; int num=0; int weight[2005]; int pd[2005]; int sum[2005]; struct data{ string s1; string s2; }d[2005]; struct ansda{ string s1; int p; }ansdata[2005]; bool cmp(ansda temp1,ansda temp2) { return temp1.s1<temp2.s1; } int getNum(string str) { if(mp.find(str)!=mp.end()) return mp[str]; mp[str]=num; num++; return num-1; } string returnStr(int x) { map<string,int>::iterator it=mp.begin(); while(it->second!=x) it++; return it->first; } int findfather(int x) { int a=x; while(x!=father[x]) { x=father[x]; } while(a!=x) { int z=a; a=father[a]; father[z]=x; } return x; } void Union(int a,int b) { if(findfather(a)!=findfather(b)) { if(weight[findfather(a)]>=weight[findfather(b)]) father[findfather(b)]=findfather(a); else father[findfather(a)]=findfather(b); } } int main() { memset(weight,0,sizeof(weight)); memset(sum,0,sizeof(sum)); int n,k; scanf("%d %d",&n,&k); string s1,s2; int t; for(int i=0;i<=2002;i++) father[i]=i; for(int i=1;i<=n;i++) { char c=getchar(); cin>>d[i].s1>>d[i].s2>>t; weight[getNum(d[i].s1)]+=t; weight[getNum(d[i].s2)]+=t; } for(int i=1;i<=n;i++) Union(getNum(d[i].s1),getNum(d[i].s2)); //printf("num:%d ",num); memset(pd,0,sizeof(pd)); int ans=0; for(int i=0;i<=num-1;i++) { pd[findfather(i)]++; sum[findfather(i)]+=weight[i]; } /*for(int i=0;i<=num-1;i++) { if(pd[i]>2 && sum[i]/2>k) ans++; }*/ /*for(int i=0;i<=num-1;i++) if(pd[i]>2 && sum[i]/2>k) cout<<returnStr(i)<<" "<<pd[i]<<endl;*/ //int count=0; for(int i=0;i<=num-1;i++) { if(pd[i]>2 && sum[i]/2>k) { ansdata[ans].s1=returnStr(i); ansdata[ans++].p=pd[i]; } } printf("%d ",ans); sort(ansdata,ansdata+ans,cmp); for(int i=0;i<ans;i++) cout<<ansdata[i].s1<<" "<<ansdata[i].p<<endl; return 0; }
要使用sort
map这里面都是你一个一个按照进入顺序赋值的string键值对，用总num标注的，字符串对应的数字是看你插入的时候对应的num，这里面么有排序。最后结果要排序输出。
还有DFS的做法
一定一定要注意！！！！！不要给结构体用memset！！！血泪教训！！！！！！可以括号赋值什么的，养成习惯能用{}就用{}
#include<iostream> #include<map> #include<algorithm> #include<string.h> #include<string> #include<stdio.h> using namespace std; int n,k; int Adj[2005][2005]={0}; map<string,int>mp; int weight[2005]={0}; bool visit[2005]={false}; int num=0; int ans=0; struct r{ string data; int member; }f[2005]; bool cmp(r a,r b) { return a.data<b.data; } string returnStr(int a) { map<string,int>::iterator it=mp.begin(); while(it->second!=a) it++; return it->first; } int getNum(string s) { if(mp.find(s)!=mp.end()) return mp[s]; mp[s]=num; return num++; } void DFS(int x,int &amax,int &member,int &sumweight) { for(int i=0;i<num;i++) { if(Adj[x][i]>0 && visit[i]==false) { visit[i]=true; member++; if(weight[i]>weight[amax]) amax=i; sumweight+=weight[i]; //sumweight+=Adj[x][i]; DFS(i,amax,member,sumweight); } } } int main() { scanf("%d %d",&n,&k); string temp1,temp2; int t; memset(weight,0,sizeof(int)); memset(visit,0,sizeof(int)); memset(Adj,0,sizeof(int)); //memset(f,0,sizeof(struct r)); for(int i=1;i<=n;i++) { cin>>temp1>>temp2>>t; Adj[getNum(temp1)][getNum(temp2)]+=t; Adj[getNum(temp2)][getNum(temp1)]+=t; weight[getNum(temp1)]+=t; weight[getNum(temp2)]+=t; } for(int i=0;i<=num-1;i++) { if(visit[i]==false) { int tempmax=i; int tempmember=1; int tempweight=weight[i]; visit[i]=true; DFS(i,tempmax,tempmember,tempweight); if(tempweight/2>k && tempmember>2) { f[ans].data=returnStr(tempmax); f[ans++].member=tempmember; } } } sort(f,f+ans,cmp); cout<<ans<<endl; for(int i=0;i<=ans-1;i++) { cout<<f[i].data<<" "<<f[i].member<<endl; } return 0; }
#include<iostream> #include<string> #include<map> #include<algorithm> using namespace std; const int maxn=2010; map<string,int> stringToInt; int ans=0; struct r{ string head; int numMember; }f[maxn]; bool cmp(r a,r b) { return a.head<b.head; } string returnStr(int i) { map<string,int>::iterator it=stringToInt.begin(); while(it->second!=i) { it++; } return it->first; } int G[maxn][maxn]={0},weight[maxn]={0}; int n,k,numPerson=0; bool vis[maxn]={false}; int change(string str) { if(stringToInt.find(str)!=stringToInt.end()) return stringToInt[str]; stringToInt[str]=numPerson; //intToString[numPerson]=str; return numPerson++; } void DFS(int nowVisit,int &head,int &numMember,int &totalValue) { for(int i=0;i<numPerson;i++) { if(G[nowVisit][i]>0 && vis[i]==false) { vis[i]=true; totalValue+=weight[i]; G[nowVisit][i]=G[i][nowVisit]=0; numMember++; if(weight[i]>weight[head]) { head=i; } DFS(i,head,numMember,totalValue); } } } int main() { int w; string str1,str2; cin>>n>>k; for(int i=0;i<n;i++) { cin>>str1>>str2>>w; int id1=change(str1); int id2=change(str2); weight[id1]+=w; weight[id2]+=w; G[id1][id2]+=w; G[id2][id1]+=w; } for(int i=0;i<numPerson;i++) { if(vis[i]==false) { int head=i,numMember=1,totalValue=weight[i]; vis[i]=true; DFS(i,head,numMember,totalValue); if(numMember>2 && totalValue/2>k) { //Gang[returnStr(head)]=numMember; f[ans].head=returnStr(head); f[ans++].numMember=numMember; } } } /*cout<<Gang.size()<<endl; map<string,int>::iterator it; for(it=Gang.begin();it!=Gang.end();it++) cout<<it->first<<" "<<it->second<<endl;*/ sort(f,f+ans,cmp); cout<<ans<<endl; for(int i=0;i<ans;i++) cout<<f[i].head<<" "<<f[i].numMember<<endl; return 0; }
上面纯自己写的下面是通过标程一点一点改出来的！！血泪教训不要对结构体使用memset！memset(f,0,sizeof(struct r))也不行！！
好像有说法会破坏析构函数什么的，暂时不明！总之!不要用！