用php做的网站源代码,开发一个直播app,wordpress showposts,厦门网站推广公司Problem Description现有M个人一起玩剪刀石头布#xff0c;以1#xff0d;M编号#xff0c;每人出一种#xff0c;出过不再改变#xff0c;但是我们并不知道它到底是哪一种。 #xff08;其中石头赢剪刀#xff0c;剪刀赢布#xff0c;布赢石头#xff0c;一样则平以1M编号每人出一种出过不再改变但是我们并不知道它到底是哪一种。 其中石头赢剪刀剪刀赢布布赢石头一样则平裁判用两种说法对这M个人所构成的输赢关系进行描述 一1 A B表示第A个人和第B个人出的一样。 二2 A B表示第A个人赢第B个人。 裁判对M个人用以上两种说法连说N句话其中有真的、也有假的。一句话出现以下情况就是假话否则就是真话。 1 该句话与之前的某些真话冲突 2 该句话中A或B比M大 3 该句话表示A赢A。 请根据给定的M和N输出假话数。其中1 M 10,0000 N 10,000 Input 第1行是一个自然数K代表有K组数据。每组数据以一个空行分隔其中每组数据的第1行是两个自然数M、N以空格分开。 每组数据的第2行至N1行每行是三个自然数XAB三个数之间用空格分开X1或2表示说法的种类。 Output 每组数据对应一行每行有一个整数代表假话数。 3 43 11 1 4 3 2 3 3 1 4 1 1 4 4 2 3 3 1 2 2 2 1 4 1 1 1 2 1 4 2 3 4 2 3 2 66 9 2 3 1 2 4 4 2 1 2 2 4 3 2 4 2 2 2 3 1 3 2 1 2 1 1 1 1 6 7 2 3 7 2 1 2 2 4 4 1 2 1 1 3 2 1 2 3 2 1 3 Sample Output 5 4 3 分析经典并查集 #include stdio.h
#includeiostream
using namespace std;
const int MAX_N 50010;
int set[MAX_N];
int r[MAX_N];
void init(int n)
{for (int i 0; i n; i){set[i] i;r[i] 0;}
}
int cha(int x)
{if (x set[x])return x;int tx cha(set[x]);r[x] (r[x] r[set[x]]) % 3;return set[x] tx;
}
void unite(int x, int y, int type)
{int tx cha(x);int ty cha(y);set[ty] tx;r[ty] (r[x] type - 1 - r[y] 3) % 3;return;
}
int main()
{int n(0), m(0);int xx;scanf(%d,xx);while(xx--){scanf(%d%d, n, m);init(n);int type(0), x(0), y(0);int ans(0);for (int i 1; i m; i){scanf(%d%d%d, type, x, y);if (x n || y n || (type 2 x y)){ans;continue;}if (cha(x) cha(y)){if ((r[y] - r[x] 3) % 3 ! (type - 1)){ans;}}else{(unite(x, y, type));}}printf(%d\n, ans);}
}转载于:https://www.cnblogs.com/castledrv/p/3664011.html
