首页 > 代码库 > 种类并查集
种类并查集
北京大学OJ1182
食物链
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 64641 | Accepted: 18999 |
Description
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。
Input
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
Output
只有一个整数，表示假话的数目。
Sample Input
100 71 101 1 2 1 22 2 3 2 3 3 1 1 3 2 3 1 1 5 5
Sample Output
3
source code:
#include <iostream>#include <vector>#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>using namespace std;std::vector<pair<int,int> > w;std::vector<pair<int,int> > d;int num,len,fakeNum;struct node{ int relation;//和父亲的关系，涉及到两个和两个以上的种类 int father;//父亲序号 //int value;//用于需要统计的题};std::vector<node> nodes;void init(){ for (int i = 0 ; i < num ; i++){ node nn; nn.father = i; //nn.value = http://www.mamicode.com/1; nn.relation = 0;//0代表是同一类，1代表吃掉父亲，2代表被父亲吃掉 nodes.push_back(nn); }}//不同题目这个函数会不同int getRelation(int a, int b ){//已知a = (x,y) b = (y,z),求c = (x,z) int c = 0; if(a == 0){ return b; } if (a == 1){ if(b == 0){ return 1; } if(b == 1){ return 2; } if(b == 2){ return 0; } } if (a == 2){ if(b == 0){ return 2; } if(b == 1){ return 0; } if(b == 2){ return 1; } }}//不同题目这个函数会不同int reverseRalation(int a){ if(a == 0){ return 0; } if(a == 1){ return 2; } if(a == 2){ return 1; }}void updateNode(int x, int root){//这里假设x的父亲是根节点或者是根节点的孩子 if (nodes[x].father == root){ return; } int f = nodes[x].father; //relation和value更新,不同题目规则不同 nodes[x].relation = getRelation(nodes[x].relation,nodes[f].relation); //nodes[f].value -= 1; nodes[x].father = root;}int getRoot(int x){ int fi = nodes[x].father; if (fi == x){ return fi; } int re = getRoot(fi); updateNode(x,re); return re;}void mergeUpdate(int x,int y,int xr,int yr,int relation){ nodes[yr].father = xr; //relation和value更新,不同题目规则不同 int xTOyr = getRelation(relation,nodes[y].relation); int yrTOx = reverseRalation(xTOyr); int yrTOxr= getRelation(yrTOx,nodes[x].relation); nodes[yr].relation = yrTOxr; //nodes[xr].value += nodes[yr].value;}bool isHarmonious(int x, int y, int relation){ int rTOy = reverseRalation(nodes[y].relation); int xTOy = getRelation(nodes[x].relation,rTOy); return relation == xTOy;}bool merge(int x , int y, int relation){ int xr = getRoot(x); int yr = getRoot(y); if(xr == yr){ return isHarmonious(x,y,relation); } else{ mergeUpdate(x,y,xr,yr,relation); return true; }}bool judge(int x , int y){ int xr = getRoot(x); int yr = getRoot(y); if (xr == yr){ return true; } else{ return false; }}int goodState(int type, int x, int y){ if (x>num || y > num){ return -1; } if (x==y && type!=1){ return -1; } return type-1;}struct data{ int ty; int f; int s; };std::vector<data> all;void input(){ fakeNum = 0; cin >> num >> len; init(); for (int i = 0 ; i < len ; i ++){ int ty; int f, s; scanf("%d%d%d",&ty,&f,&s); //cout << ty << " " << f << " " << s <<endl; data d; d.ty = ty; d.f = f; d.s = s; all.push_back( d ); // all.push_back(s); // if (ty == 1){ // d.push_back(make_pair<int,int>(f,s) ); // } // else{ // w.push_back(make_pair<int,int>(f,s) ); // } } for (int i = 0 ; i < len ; i ++){ int ty = all[i].ty; int f = all[i].f; int s = all[i].s; //cout << ty << " " << f << " " << s <<endl; int relation = goodState(ty , f , s); if (relation == -1){ fakeNum++; } else{ if (!merge(f-1,s-1,relation)){ fakeNum++; } } } //sort(all.begin(), all.end()); //std::vector<int>::iterator nown = unique(all.begin(), all.end()); //all.erase(nown,all.end()); //re = 0;}void calc(){}void output(){ cout << fakeNum; // cout <<num << " "<< len << endl; // for (int i = 0 ; i < d.size() ; i ++){ // cout << "1 "<<" " <<d[i].first << " " << d[i].second <<endl; // } // for (int i = 0 ; i < w.size() ; i ++){ // cout << "2 "<<" " <<w[i].first << " " << w[i].second <<endl; // } // for (int i = 0 ; i < all.size() ; i ++){ // cout << all[i]<< " "; // }}int main(){ input(); calc(); output(); return 0;}
测例生成器：
#include <iostream>#include <vector>#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>#include <ctime>#include <cstdlib>using namespace std;int N=50000,K = 100000;int main(){ srand(unsigned(time(0))); cout << N << " " << K << endl; for (int i = 0 ; i < K ; i++){ cout << rand()%2+1 << " " << rand()%int(N+double(N)*0.01)+1<< " " << rand()%int(N+double(N)*0.01)+1<<endl; } }
种类并查集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。