寻找网络公司做公司网站升级改版,优化电池充电有必要开吗,学php到做网站要多久,学做网站设计需要多少钱Problem - D - Codeforces Theofanis开始玩名为“Among them”的新网络游戏。然而#xff0c;他总是和塞浦路斯球员一起踢球#xff0c;他们都有一个相同的名字:“安德烈亚斯”(塞浦路斯最常见的名字)。在每个游戏中#xff0c;Theofanis和n个其他玩家一起玩。因为它们都有相…Problem - D - Codeforces Theofanis开始玩名为“Among them”的新网络游戏。然而他总是和塞浦路斯球员一起踢球他们都有一个相同的名字:“安德烈亚斯”(塞浦路斯最常见的名字)。在每个游戏中Theofanis和n个其他玩家一起玩。因为它们都有相同的名字所以编号从1到n。玩家在聊天中写下了m条评论。注释的结构是i j c其中i和j是两个不同的整数c是一个字符串(1 i, j n;我j;C不是冒名顶替者就是船员)。注释的意思是玩家i说玩家j扮演角色c。冒名顶替者总是撒谎而船员总是说真话。帮助Theofanis找出所有其他塞浦路斯玩家中冒名顶替者的最大可能数量或者确定评论彼此矛盾(参见注释中的进一步解释)。注意每个玩家只有一个角色:冒名顶替者或船员。输入第一行包含一个整数t (1 t 104)——测试用例的数量。下面是每个测试用例的描述。每个测试用例的第一行包含两个整数n和m (1 n 2-105;0 m 5-105) -除Theofanis之外的玩家数量和评论数量。接下来的m行每一行都包含一个由结构为“i j c”的玩家所做的评论其中i和j是两个不同的整数c是一个字符串(1 i, j≤n;I # j;C不是冒名顶替者就是船员)。同一对(i, j)可以有多个注释。保证所有n的和不超过2-105所有m的和不超过5 -105。输出对于每个测试用例打印冒名顶替者的最大可能数量的整数。如果注释相互矛盾则打印-1。
Example
input
Copy
5
3 2
1 2 imposter
2 3 crewmate
5 4
1 3 crewmate
2 5 crewmate
2 4 imposter
3 4 imposter
2 2
1 2 imposter
2 1 crewmate
3 5
1 2 imposter
1 2 imposter
3 2 crewmate
3 2 crewmate
1 3 imposter
5 0output
Copy
2
4
-1
2
5
题解: 首先我们应该知道一个很重要的规律,如果c是crewmate(后面用1代表),a和b身份相同,否则身份不同
假设a - b 1
1.a 1,b 1
2.a 0,b 0
假设a- b 0
1.a 1,b 0
2.a 0,b 1
根据这个性质,我们可以建造一个二分图
如果两点身份不同,直接连边
如果两点身份相同,建造一个虚点,并且两边
最后利用染色法,看构建的二分图是否有冲突即可
#includeiostream
#includestring
#includevector
#includecstring
#includealgorithm
#includequeue
#includemap
using namespace std;
typedef long long ll;
#define int long long
typedef pairint,int PII;
int col[1000060];
vector int p[1000060];
int ca,cb;
int n,m;
int dfs(int x,int c)
{col[x] c;if(x n){if(c 1)ca;elsecb;}for(auto ne:p[x]){if(!col[ne]){if(!dfs(ne,3 - c))return 0;}else if(col[ne] col[x])return 0;}return 1;
}
void solve()
{cin n m;int ans 0;for(int i 1;i n m;i){p[i].clear();col[i] 0;}int n1 n;for(int i 1;i m;i){int a,b;string c;cin a b c;if(c[0] i){p[a].push_back(b);p[b].push_back(a);}else{n1;p[a].push_back(n1);p[n1].push_back(a);p[b].push_back(n1);p[n1].push_back(b);}}for(int i 1;i n1;i){if(col[i])continue;ca 0,cb 0;if(dfs(i,1)){ans max(ca,cb);}else{cout -1\n;return ;}}cout ans \n;}
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);int t 1;cin t;
// scanf(%lld,t);while (t--) {solve();}return 0;
}
