网站后台如何添加关键词,什么是营销网站建设,杭州网站基建,织梦网站地图制作题干#xff1a;
动物王国中有三类动物A,B,C#xff0c;这三类动物的食物链构成了有趣的环形。A吃B#xff0c; B吃C#xff0c;C吃A。 现有N个动物#xff0c;以1#xff0d;N编号。每个动物都是A,B,C中的一种#xff0c;但是我们并不知道它到底是哪一种。 有人用两…题干
动物王国中有三类动物A,B,C这三类动物的食物链构成了有趣的环形。A吃B B吃CC吃A。 现有N个动物以1N编号。每个动物都是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就是假话。 你的任务是根据给定的N1 N 50,000和K句话0 K 100,000输出假话的总数。
Input
第一行是两个整数N和K以一个空格分隔。 以下K行每行是三个正整数 DXY两数之间用一个空格隔开其中D表示说法的种类。 若D1则表示X和Y是同类。 若D2则表示X吃Y。
Output
只有一个整数表示假话的数目。
Sample Input
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5Sample Output
3 解题报告
其中在判断真假话之后如果是真话就必须更新这句真话。
其实判断此类并查集问题的关键是先搞清楚这两个节点之间的关系。
比如 1 2 3这个操作如果要你判断2和3是同类这一个命题。
那么我们就找2和3相对于祖宗的性质比如2被其祖宗吃3吃其祖宗那么如果2和3是同一个祖宗同一个集合显然这个命题不成立。
如果2和3不是同一个祖宗那么我们现在就需要合并两个祖宗因此打表一下就能得出两个祖宗之间的关系。
2的操作也是这个原理。 贴一份测试数据POJ - 食物链 - 测试数据 AC代码
#includeiostream
#includecstdio
#includecstring
#includealgorithmusing namespace std;
const int MAX50000 5;
int f[MAX];
int rank[MAX];
int n,k,ans;
int getf(int x) {if(x!f[x]) {int tmpgetf(f[x]);rank[x](rank[x]rank[f[x] ] ) % 3;f[x]tmp;}return f[x];
}
bool merge(int d,int x,int y) {int t1getf(x);int t2getf(y);if(t1t2) {if((rank[y]-rank[x]3)%3!d)return 1;else return 0;}else {f[t2]t1;rank[t2](rank[x]-rank[y]d3) % 3;return 0;}}
int main()
{int d,u,v;scanf(%d%d,n,k);ans0;//初始化 for(int i1;in;i) {f[i]i;rank[i]0;}while(k--) {scanf(%d %d %d,d,u,v);if(un||vn||(uvd2) ) {ans;continue;}if(merge(d-1,u,v) ) ans;}printf(%d\n,ans);return 0;
} 附一个博客的讲解https://blog.csdn.net/c0de4fun/article/details/7318642
Part I - 权值(relation)的确定。 我们根据题意森林中有3种动物。A吃BB吃CC吃A。 我们还要使用并查集那么我们就以动物之间的关系来作为并查集每个节点的 权值。 注意我们不知道所给的动物题目说了输入只给编号所属的种类。 所以我们可以用动物之间“相对”的关系来确定一个并查集。 0 - 这个节点与它的父节点是同类 1 - 这个节点被它的父节点吃 2 - 这个节点吃它的父节点。 注意这个0,1,2所代表的意义不是随便制定的我们看题目中的要求。 说话的时候第一个数字下文中设为d指定了后面两种动物的关系 1 - X与Y同类 2 - X吃Y 我们注意到当 d 1的时候( d - 1 ) 0也就是我们制定的意义 当 d 2的时候( d - 1 ) 1代表Y被X吃也是我们指定的意义。 所以这个0,1,2不是随便选的 Part II - 路径压缩以及节点间关系确定 确定了权值之后我们要确定有关的操作。 我们把所有的动物全初始化。 struct Animal { int num; //该节点node的编号 int parent; //该node的父亲 int relation; //该node与父节点的关系0同类1被父节点吃2吃父节点 }; Animal ani[50010]; 初始化为 For i 0 to N do ani[i].num i; ani[i].parent i; ani[i].relation 0 ; //自己和自己是同类 End For (1)路径压缩时的节点算法 我们设A,B,C动物集合如下为了以后便于举例 A { 1 , 2 , 3 ,4 ,5 } B { 6 , 7 , 8 ,9 ,10} C { 11, 12, 13,14,15} 假如我们已经有了一个集合分别有3个元素 SET1 {1,2}我们规定集合中第一个元素为并查集的“代表” 假如现在有语句 2 2 6 这是一句真话 2是6的父亲 ani[6].parent 2; ani[6].relation 1; 那么6和1的关系如何呢 ani[2].parent 1; ani[2].relation 0; 我们可以发现6与2的关系是 1. 通过穷举我们可以发现 ani[now].parent ani[ani[now].parent].parent; ani[now].relation ( ani[now].relation ani[now.parent].relation ) % 3; 这个路径压缩算法是正确的 关于这个路径压缩算法还有一点需要注意的地方我们一会再谈 注意根据当前节点的relation和当前节点父节点的relation推出 当前节点与其父节点的父节点的relation这个公式十分重要 它推不出来下面都理解不了自己用穷举法推一下 好吧为了方便伸手党我给出穷举过程 i j 爷爷 父亲 儿子 儿子与爷爷 0 0 (i j)%3 0 0 1 (i j)%3 1 0 2 (i j)%3 2 1 0 (i j)%3 1 1 1 (i j)%3 2 1 2 (i j)%3 0 2 0 (i j)%3 2 2 1 (i j)%3 0 2 2 (i j)%3 1 嗯这样可以看到( 儿子relation 父亲relation ) % 3 儿子对爷爷的relation 这就是路径压缩的节点算法 (2) 集合间关系的确定 在初始化的时候我们看到每个集合都是一个元素就是他本身。 这时候每个集合都是自洽的集合中每个元素都不违反题目的规定 注意我们使用并查集的目的就是尽量的把路径压缩使之高度尽量矮 假设我们已经有一个集合 set1 {1,2,7,10} set2 {11,4,8,13},每个编号所属的物种见上文 set3 {12,5,4,9} 现在有一句话 2 13 2 这是一句真话,X 13,Y 2 我们要把这两个集合合并成一个集合。 直接 int a findParent(ani[X]); int b findParent(ani[Y]); ani[b].parent a; 就是把Y所在集合的根节点的父亲设置成X所在集合的根节点。 但是但是 Y所在集合的根结点与X所在集合的根节点的关系要怎么确定呢 我们设X,Y集合都是路径压缩过的高度只有2层 我们先给出计算的公式 ani[b].relation ( 3 - ani[Y].relation ( d - 1 ) ani[X].relation) % 3; 这个公式是分三部分这么推出来的 第一部分好理解的一部分 ( d - 1 ) :这是X和Y之间的relationX是Y的父节点时Y的relation就是这个 3 - ani[Y].relation 根据Y与根节点的关系逆推根节点与Y的关系 这部分也是穷举法推出来的我们举例 j 子 父相对于子的relation即假如子是父的父节点那么父的relation应该是什么因为父现在是根节点所以父.relation 0我们只能根据父的子节点反推子跟父节点的关系 0 ( 3 - 0 ) % 3 0 1父吃子 ( 3 - 1 ) % 3 2 //父吃子 2子吃父) ( 3 - 2 ) % 3 1 //子吃父一样的哦亲 —————————————————————————————————————————————————————— 我们的过程是这样的 把ani[Y]先连接到ani[X]上再把ani[Y]的根节点移动到ani[X]上最后把ani[Y]的根节点移动到ani[X]的根节点上这样算relation的 还记得么如果我们有一个集合压缩路径的时候父子关系是这么确定的 ani[爷爷].relation ( ani[父亲].relation ani[儿子].relation ) % 3 我们已知道,( d - 1 )就是X与Y的relation了 而 (3 - ani[Y].relation)就是 以Y为根节点时他的父亲的relation 那么 我们假设把Y接到X上也就说现在X是Y的父亲Y原来的根节点现在是Y的儿子 Y的relation ani[Y]根节点相对于ani[Y]的relation ( ( d - 1 ) ( 3 - ani[Y].relation) ) % 3 就是ani[Y]的父亲节点与ani[X]的relation了 那么不难得到ani[Y]的根节点与ani[X]根节点的关系是 ( ( d - 1 ) ( 3 - ani[Y].relation) ani[X].relation ) % 3 -应用了同余定理 注意这个当所有集合都是初始化状态的时候也适用哦 还是以最开头我们给的三个集合分别代表三个物种为例 2 1 6 带入公式 ani[6].relation ( ( 2 - 1 ) ( 3 - 0 ) 0 ) % 3 1 也就是6被1吃 Part III - 算法正确性的证明 首先两个自洽的集合合并以后仍然是自洽的 这个不难想吧数学上有个什么对称性定理跟他很像的。 如果理解不了就这么想 当set1和set2合并之后set2的根节点得到了自己关于set1根节点的 正确relation值变成了set1根节点的儿子那么 set2的所有儿子只要用 ( ani[X].relation ani[Y].relation ) % 3就能得到自己正确的relation值了 所以说针对不在同一集合的两个元素的话除非违背了2和3否则永远是真的 无论这句话说的是什么我们都可以根据所给X,Y推出两个子节点之间应有的关系这个关系一确定所有儿子的关系都可以确定 其实所有的不同集合到最后都会被合并成一个集合的。 我们只要在一个集合中找那些假话就可以了。 首先如何判断 1 X Y是不是假话。//此时 d 1 if ( X 和 Y 不在同一集合) Union(x,y,xroot,yroot,d) else if x.relation ! y.relation -假话 其次如何判断 2 X Y是不是假话 //此时d 2 if ( X 和 Y 不在同一集合 Union(x,y,xroot,yroot,d) else (ani[y].relation 3 - ani[x].relation ) % 3 ! 1 -假话 这个公式是这么来的 3 - ani[x].relation得到了根节点关于x的relation ani[y] 3 - ani[x].relation得到了y关于x的relation 所以只要y关于x的relation不是1就是y不被x吃的话这句话肯定是假话 (2)路径压缩要特别注意的一点错在这里要检讨自己 路径压缩的时候记得要 先findParent再给当前节点的relation赋值。 否则有可能因为当前节点的父节点的relation不正确而导致错的稀里哗啦。 例子 set1 {1,2,7,10} set2 {3,4,8,11} set3 {12,5,14,9} Union(1,3,1,3,1) Union(3,12,3,12,2) 1 5 1 算5的relation 如果不先更新parent的relation算出来应该是 ( 3 - 0 0 1 ) % 3 15被1吃显然不对 这里面 0的那个0是指根节点 12 的relation未更新这里的0是指12与11的relation 如果更新完了的话应该是 ( 3 - 0 2 1 ) % 3 0 ,5与1是同一物种对了 这里面的 2 是更新节点12的relation12与1的relation #include cstdio
#include cstdlib
#include cstring
#include iostreamusing namespace std;
const int c0de4fun 50010;//动物个数的最大值
///指明父节点与自己的关系0同类1被吃2吃父
const int SAME 0;
const int ENEMY 1;
const int FOOD 2;
struct Animal
{int parent;int num;int relation;
};
Animal ani[c0de4fun];
long ans;
int findParent(Animal* node)
{///Wrong Answer 因为这个函数写错了///这个函数得是“自洽的”///就是说得保证每个元素的父亲的relation是对的///再算自己的relation///因为自己的relation和父亲的relation有关///这就是为什么要先findParent再relation更新的原因int tmp;if( node-parent node-num )return node-parent;tmp node-parent;
#ifdef DBGprintf(Animal %d s Parent is %d\n,node-num,node-parent);
#endif// node-relation ( ani[node-parent].relation node-relation ) % 3;node-parent findParent(ani[node-parent]);node-relation ( ani[tmp].relation node-relation ) % 3;return node-parent;
}
void Union(int x,int y,int a,int b,int d)
{ani[b].parent a;///rootY.parent rootX.parent;ani[b].relation ( (3 - ani[y].relation) (d - 1) ani[x].relation) % 3;
}void init_Animal(int n)
{for(int i 1 ; i n ; i){ani[i].num i;ani[i].parent i;ani[i].relation SAME;}
}
int main(int argc,char* argv[])
{int N,K;int d,X,Y;
#ifdef INPUTfreopen(b:\\acm\\poj1182\\input.txt,r,stdin);
#endifscanf(%d%d,N,K);init_Animal(N);for(int i 0 ; i K ; i){scanf(%d%d%d,d,X,Y);if( X N || Y N)ans;else{if(d 2 X Y)ans;else{int a findParent(ani[X]);int b findParent(ani[Y]);if ( a ! b ){///xy不在同一集合中Union(X,Y,a,b,d);}else{switch(d){case 1:if(ani[X].relation ! ani[Y].relation)ans;break;case 2:if(((ani[Y].relation 3 - ani[X].relation) % 3 ) ! 1)ans;break;}}}}}printf(%d\n,ans);return 0;
}
