Codeforces Round #747 (Div.2) D. The Number of Imposters

题意:

\(n\)个人,每个人要么是敌人,要么是朋友。已知敌人一定说假话,朋友一定说真话,给出\(m\)句形如\(i,j,c\)的话,表示第\(i\)个人说第\(j\)个人的身份是\(c\)​,问敌人的最大可能数量是多少。

\(1\le n\le 2e5\)

题解:

\(2-SAT\)​只能判是否有解,找出的不是最优解

注意到如果A说B为朋友,那么A和B的身份是相同的(A假B也假,A真B也真),否则A和B身份相反(A假B真,A真B假)

也就是说,\(n\)个点中每个点要么是黑色,要么是白色,并且已知了一些关系(某些点颜色相同/相反),

建图并黑白染色,使得染色方案没有冲突(是二分图)

在颜色相同的点之间连边权0的边,异色点之间连边权为1的边,每次要么把点染成0,要么染成1,dfs检查染色是否按照(\(col[u] \ xor\ w(u,v)=col[v]\)​​),若不是则不合法

点与点之间的限制关系可以通过建图连边,然后在边上dfs/bfs传递和检查

// Problem: D. The Number of Imposters
// Contest: Codeforces - Codeforces Round #747 (Div. 2)
// URL: https://codeforces.com/contest/1594/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
#define ll long long
int n, m, k, tot;
int rd() {
	int s = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') {s = s * 10 + c - '0'; c = getchar();}
	return s * f;
}
struct edge {
	int v, w, nxt;
}e[1000007];
int head[maxn], eid, col[maxn], ans, ans1, ans2;
char str[20];
void init() {
	for (int i = 1; i <= n; i++) head[i] = col[i] = -1;
	eid = 0;
}
void insert(int u, int v, int w) {
	e[eid].v = v;
	e[eid].w = w;
	e[eid].nxt = head[u];
	head[u] = eid++;
}
void dfs(int u, int c) {
	col[u] = c;
	//printf("u == %d\n", u);
	if (c == 0) ans1++;
	else ans2++;
	for (int i = head[u]; ~i; i = e[i].nxt) {
		int v = e[i].v;
		if (col[v] == -1) {
			dfs(v, c^e[i].w);
		} else {
			if ((col[v]^col[u]) != e[i].w) {
				//printf("u v w == %d %d %d\n", u, v, e[i].w);
				ans = -999999999;
			}
		}
	}
}
int main() {
	int T = rd();
	while (T--) {
		n = rd(), m = rd();
		ans = 0;
		init();
		for (int i = 1; i <= m; i++) {
			int u = rd(), v = rd();
			scanf("%s", str);
			if (str[0] == 'i') {
				insert(u, v, 1);
				insert(v, u, 1);
			} else {
				insert(u, v, 0);
				insert(v, u, 0);
			}
		}
		for (int i = 1; i <= n; i++) {
			if (col[i] == -1) {
				ans1 = ans2 = 0;
				dfs(i, 0);
				ans += max(ans1, ans2);
			}
		}
		printf("%d\n", ans < 0 ? -1 : ans);
	}
}
上一篇:Codeforces Round 747


下一篇:747. 数组的左上半部分