Difference of Clustering HDU - 5486
题意：有n个实体，新旧两种聚类算法，每种算法有很多聚类，在同一算法里，一个实体只属于一个聚类，然后有以下三种模式。
第一种分散,新算法的某几个聚类是旧算法某个聚类的真子集。
第二种聚合,旧算法的某几个聚类是新算法某个聚类的真子集。
第三种1:1,新算法的某个聚类跟旧算法某个聚类相同。
问每种模式存在多少个?
实路上很明了，就是模拟，而且每个实体最多遍历到一次，所以时间上不用担心。
先把聚类的编号hash，把每个实体分配到相应的聚类里，然后遍历新算法的所有聚类，再遍历每个聚类里的每个实体，用set保存这个实体相应的旧算法的聚类。
然后就是分情况讨论，如果set里的元素大于1，很明显就是分散，我们遍历set里的旧算法的聚类，然后遍历实体，看实体的编号是不是都对应当前遍历的新算法的编号
如果set里元素刚好是1，就看这个唯一对应的旧算法的聚类大小，如果等于当前遍历的新算法的大小，就是1:1了，否则我们考虑聚合的情况，处理跟分散差不多
遍历这个旧算法的聚类里的实体，用set保存这个实体相应的新算法的聚类，遍历set里的新算法的聚类，然后遍历实体，看实体的编号是不是都对应这个旧算法的编号
这里要注意的就是标记一下遍历的新算法的聚类的编号，然后后面遍历到这个聚类直接跳过就行。
具体实现上，stl用的好的话很好实现的，需要注意的就是内存的问题。clear是不会清空内存的，所有会超内存，所以用swap，
还有二维vector，vector<int> pp1[N],pp2[N]这样开的话也会超内存，改成vector< vector<int> > 动态分配内存就OK了。
主要是想保存一些这个swap和二维vector降低内存的方法，还有无序map。解法的话网上有个思路，把给出的关系转换成图，然后dfs判断点的度数就行了。
1 #include<cstdio> 2 #include<tr1/unordered_map> 3 #include<vector> 4 #include<set> 5 using namespace std; 6 typedef long long ll; 7 const int N=1e6+2; 8 const ll M=1e10+11; 9 tr1::unordered_map<ll,int> mmp; 10 vector< vector<int> > pp1,pp2;//记录相应的聚类里的实体 11 set<int> temp; 12 bool vis[N]; 13 int match1[N],match2[N];//记录实体对应的聚类 14 int main(){ 15 int t=1,T,n,cnt1,cnt2,id1,id2; 16 ll c1,c2; 17 scanf("%d",&T); 18 while(t<=T){ 19 cnt1=cnt2=0; 20 tr1::unordered_map<ll,int>().swap(mmp); 21 vector< vector<int> >().swap(pp1); 22 vector< vector<int> >().swap(pp2); 23 pp1.push_back(vector<int>()); 24 pp2.push_back(vector<int>()); 25 scanf("%d",&n); 26 for(int i=0;i<=n;i++) vis[i]=false; 27 for(int i=1;i<=n;i++){ 28 scanf("%lld%lld",&c1,&c2); 29 c2+=M; 30 if(!mmp[c1]) mmp[c1]=++cnt1; 31 if(!mmp[c2]) mmp[c2]=++cnt2; 32 id1=mmp[c1];id2=mmp[c2]; 33 if(cnt1>=(int)pp1.size()) 34 pp1.push_back(vector<int>()); 35 if(cnt2>=(int)pp2.size()) 36 pp2.push_back(vector<int>()); 37 pp1[id1].push_back(i); 38 pp2[id2].push_back(i); 39 match1[i]=id1; 40 match2[i]=id2; 41 } 42 int ans1=0,ans2=0,ans3=0; 43 for(int i=1;i<=cnt1;i++){ 44 if(vis[i]) continue; 45 set<int>().swap(temp); 46 for(int j=0;j<(int)pp1[i].size();j++) 47 temp.insert(match2[pp1[i][j]]); 48 if((int)temp.size()>1){ 49 bool flag=true; 50 for(set<int>::iterator it=temp.begin();it!=temp.end()&&flag;it++){ 51 id2=*it; 52 for(int k=0;k<(int)pp2[id2].size()&&flag;k++){ 53 id1=pp2[id2][k]; 54 if(match1[id1]!=i) flag=false; 55 } 56 } 57 if(flag) ans1++; 58 }else{ 59 id2=*temp.begin(); 60 if((int)pp2[id2].size()!=(int)pp1[i].size()){ 61 set<int>().swap(temp); 62 for(int j=0;j<(int)pp2[id2].size();j++){ 63 id1=pp2[id2][j]; 64 if(match1[id1]!=i) temp.insert(match1[id1]); 65 } 66 bool flag=true; 67 for(set<int>::iterator it=temp.begin();it!=temp.end();it++){ 68 id1=*it; 69 vis[id1]=true; 70 for(int k=0;k<(int)pp1[id1].size();k++){ 71 int id3=pp1[id1][k]; 72 if(match2[id3]!=id2){ 73 flag=false; 74 break; 75 } 76 } 77 } 78 if(flag) ans2++; 79 }else ans3++; 80 } 81 } 82 printf("Case #%d: %d %d %d\n",t++,ans1,ans2,ans3); 83 } 84 return 0; 85 }