D. The Number of Imposters(二分图染色)
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 0
output
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
根据这个性质,我们可以建造一个二分图
如果两点身份不同,直接连边
如果两点身份相同,建造一个虚点,并且两边
最后利用染色法,看构建的二分图是否有冲突即可
#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,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;
}