CFdiv2-The Number of Imposters-(两种点集图上染色问题总结)

D

题意：
就是给你n个人，和m句话。每句话是a说b是好人或者坏人。问你这些人中最多有多少坏人。当然如果这m句话有错误出现驳论那么就输出-1。

思考：
1.这是很久之前做的题了。有两种做法，种类并查集和两种点集图上染色。这里就整理第二种做法。首先，这些人可以很明显的去合并和分类，意思就是，a说b是好人，那么a和b就在一类，如果不是好人，那么就不在一类。
2.那么可以对a和b建边，权值为1的时候代表a和b是一类，权值为0的时候代表a和b不是一类。建立完边后呢？那么一个连通块的人，只要确定了一个人的身份，剩下的身份就全部出来了。那么这里面颜色为1的和为2的，就可以随意转化，为1的可以是好人也可以是坏人。
3.那么既然有可能出现驳论，那么怎么判断呢？如果a说b是好人，那么a和b肯定是同一颜色的，因为他俩是一个帮派，无论是好人帮派还是坏人帮派。如果a搜到b的时候，发现b此时已经有颜色了，并且还和自己的颜色不一样，那么就出现驳论了。同理a说是b是坏人，但是a和b的颜色一样了，那么也是错误的。然后怎么求最多的坏人呢？因为一个连通块里面，颜色1和2可以随意转化，那么就让颜色多的是坏人即可。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int va[N];
int col[N];
int cnt[2];
int suc = 1;

vector<PII > e[N];

void dfs(int now)
{
	cnt[col[now]]++;
	for(auto t:e[now])
	{
		int spot = t.fi,w = t.se;
		if(!col[spot])
		{
			if(w==1) col[spot] = 3-col[now];
			else col[spot] = col[now];
			dfs(spot);
		}
		else
		{
			if(w==1&&col[spot]==col[now]) suc = 0;
			if(w==0&&col[spot]!=col[now]) suc = 0;
		}
	}	
}

signed main()
{
	IOS;
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			col[i] = 0;
			e[i].clear();
		}
		while(m--)
		{
			int a,b;string s;
			cin>>a>>b>>s;
			if(s=="imposter")
			{
				e[a].pb({b,1});
				e[b].pb({a,1});
			}
			else
			{
				e[a].pb({b,0});
				e[b].pb({a,0});
			}
		}
		suc = 1;
		int ans = 0;
		for(int i=1;i<=n;i++)
		{
			if(!col[i])
			{
				col[i] = 1;
				cnt[1] = cnt[2] = 0;
				dfs(i);
				ans += max(cnt[1],cnt[2]);
			}
		}
		if(suc) cout<<ans<<"\n";
		else cout<<-1<<"\n";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

Div1+2-The Door Problem

题意：
就是给你n个门，有的是打开的状态有的是关闭的状态，然后给你m个开关，每个开关控制一些门。按下开关，可以让他控制的所有的门变成相反的状态。然后每个门就有两个开关控制它。现在问你是否可以按下某些开关，让这些门全部变成打开或者关闭的状态。

思考：
1.当时看到这题，对于开着的门，它的两个开关要么都按要么都不按，对于关着的门，他的两个开关只能按其中一个。那么我就想了并查集，如果开着的，那么两个开关必须在一个集合。然后再对关着的门看看他的两个开关是否在一个集合里面，如果在那么代表这两个开关必须同时选，所以就不满足自己了，但是发现错了。因为还有别的可能，然后推了推我发现这是个类似二分图的东西，有好几个连通块去处理啥的。注意这里不是二分图，自己的理解有误。到这里就感觉卡死做不下去了。
2.然后看了下提示，说是把门当边，两个开关当点，建图。看到这，我就想到了以前做的说谎者。如果门是开着的，那么a开关和b开关是肯定在一个集合里面的，所以a和b连一条为1的边。如果关着的就连为0的边。
3.我都想到这里了，但是不知道脑子里想的什么，总感觉这该怎么去颜色呢？因为对于一个连通块，你不能随便去颜色，会对别的连通块有影响。其实这里不同的连通块肯定是没啥影响的呀，都没有交集。这里我认为有影响是因为我第一个做法写的时候，不同的连通块之间是有·影响的，所以就…。
4.那么此时缓过来，就可以发现对图颜色就行了，如果没有驳论的话那么就可以让整个图都满足我建立的边的条件，那么就可以让所有的门都是开着的。
5.还有个值得注意的点就是，判断是否颜色出现错误的时候，要在dfs里面跑的时候就判断。如果你出来再判断，一些没边的点也会颜色，可能就会对答案有影响(可能，这个还是看你写题的姿势)。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int va[N];
int col[N];
int suc = 1;

vector<int > v[N];
vector<PII > e[N];

void dfs(int now)
{
	for(auto t:e[now])
	{
		int spot = t.fi,w = t.se;
		if(!col[spot])
		{
			if(w==1) col[spot] = col[now];
			else col[spot] = 3-col[now];
			dfs(spot);
		}
		else
		{
			if(w==1&&col[spot]!=col[now]) suc = 0;
			if(w==0&&col[spot]==col[now]) suc = 0;
		}
	}
}

signed main()
{
	IOS;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>va[i];
	for(int i=1;i<=m;i++)
	{
		cin>>k;
		while(k--)
		{
			int x;
			cin>>x;
			v[x].pb(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		int a = v[i][0],b = v[i][1];
		e[a].pb({b,va[i]});
		e[b].pb({a,va[i]});
	}
	for(int i=1;i<=m;i++)
	{
		if(!col[i]) col[i] = 1,dfs(i);
	}
	suc?cout<<"YES\n":cout<<"NO\n";
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

CF-Graph Coloring
需要用这个连接提交题目

题意：
就是给你n个点和m条边，每条边有一个颜色黑或者白。然后你可以在一个点进行操作，可以使得这个点的所有边的颜色都反转。问你是否可以通过操作，使得所有边的颜色都一样，如果可以输出最小的操作次数，和操作的点。如果不可以就输出-1。

思考：
1.显然，这个题和上一个题是一样的。我们可以把黑边看成开的门，或者白边看成开的门。注意这两种看法答案是不一样的，不能随意转变。比如对于黑边，那么他的两个点是同一类的，对于白边他的两个点不是同一类的。这样就分成了两类。
2.但是这个题目要求最小操作次数，那么我们可以分别求这两种情况，最后取个最小值就可以了。如果两种看法都不行，那么就是无解。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

struct node{
	int a,b,c;
};

int T,n,m,k;
node va[N];
int col[N];
int cnt[3];
int suc = 1;
int minn = inf;

vector<int > v1,v2;
vector<int > anw;
vector<PII > e[N];

void dfs(int now)
{
	if(col[now]==1) v1.pb(now);
	else v2.pb(now);
	cnt[col[now]]++;
	for(auto t:e[now])
	{
		int spot = t.fi,w = t.se;
		if(!col[spot])
		{
			if(w==1) col[spot] = col[now];
			else col[spot] = 3-col[now];
			dfs(spot);
		}
		else
		{
			if(w==1&&col[spot]!=col[now]) suc = 0;
			if(w==0&&col[spot]==col[now]) suc = 0;
		}
	}
}

void solve(int op)
{
	suc = 1;int ans = 0;
	for(int i=1;i<=n;i++)
	{
		col[i] = 0;
		e[i].clear();
	}
	for(int i=1;i<=m;i++)
	{
		int a = va[i].a,b = va[i].b,c = va[i].c;
		if(op) c ^= 1;
		e[a].pb({b,c});
		e[b].pb({a,c});		
	}
	vector<int > v;
	for(int i=1;i<=n;i++)
	{
		if(!col[i])
		{
			col[i] = 1;
			cnt[1] = cnt[2] = 0;
			v1.clear();v2.clear();
			dfs(i);
			ans += min(cnt[1],cnt[2]);
			if(cnt[1]<cnt[2]) for(auto t:v1) v.pb(t);
			else for(auto t:v2) v.pb(t);
		}
	}
	if(suc&&minn>ans)
	{
		minn = ans;
		anw = v;
	}
}

signed main()
{
	IOS;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;char op;
		cin>>a>>b>>op;
		if(op=='B') va[i] = {a,b,1};
		else va[i] = {a,b,0};
	}
	solve(0);solve(1);
	if(minn==inf) cout<<-1<<"\n";
	else
	{
		cout<<minn<<"\n";
		for(auto t:anw) cout<<t<<" ";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

Acwing-奇偶游戏

题意：
有一个n的01数组，然后小A会说m句话，每次他会说l到r这段区间内有奇数个1还是有偶数个1。当他说某句话，但是这句话会和前面产生矛盾的时候就停止。问他说的正确的话有多少。

思考：
1.其实这种区间再合并问题，一般都是带权并查集去做的。但是这个题也可以分为两种点集染色去做。现在的目的就是如何对点进行分类。那么边就是小A的话，点就是l和r。如果l到r是偶数个1，可以想到什么？如果维护一个前缀和，维护的是1的个数。那么l-1和r这两个点的前缀和的1的个数是不是奇偶性相同的？所以l-1和r是同一类的，否则就不是。
2.然后图可以建立了，但是有矛盾的时候就退出，所以你不知道把多少条边放进去，然后再染色。所以刚开始还想，每次加一条边，染色一次，但是这样是错的，因为同一个连通块的点必须一次染完，不能分开染色再去合并。
3.所以到这里必须要先建图再染色，但是我不知道什么时候停止怎么建图？那么就可以二分呀，二分停止的点，每次建图，看看是否有矛盾，没有就继续。所以题目就要一步一步的去解决。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

struct node{
	int a,b,c;
};

int T,n,m,k;
node va[N];
int suc = 1;

vector<int > v;
map<int,int > col;
vector<PII > e[N];

int get(int x)
{
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}

void dfs(int now)
{
	for(auto t:e[now])
	{
		int spot = t.fi,w = t.se;
		if(!col[spot])
		{
			if(w==1) col[spot] = col[now];
			else col[spot] = 3-col[now];
			dfs(spot);
		}
		else
		{
			if(w==1&&col[spot]!=col[now]) suc = 0;
			if(w==0&&col[spot]==col[now]) suc = 0;
		}
	}	
}

bool check(int mid)
{
	suc = 1;col.clear();
	for(int i=0;i<=2*m+10;i++) e[i].clear();
	for(int i=1;i<=mid;i++)
	{
		int a = va[i].a,b = va[i].b,c = va[i].c;
		e[a].pb({b,c});
		e[b].pb({a,c});
	}
	for(int i=1;i<=mid;i++)
	{
		int a = va[i].a;
		if(!col[a])
		{
			col[a] = 1;
			dfs(a);
		}
	}
	return suc;
}

signed main()
{
	IOS;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;string s;
		cin>>a>>b>>s;
		if(s=="even") va[i] = {a-1,b,1};
		else va[i] = {a-1,b,0};
		v.pb(a-1);v.pb(b);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=m;i++)
	{
		va[i].a = get(va[i].a);
		va[i].b = get(va[i].b);
	}
	int l = 0,r = m;
	while(l<r)
	{
		int mid = (l+r+1)>>1;
		if(check(mid)) l = mid;
		else r = mid-1;
	}
	cout<<l;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

总结：
看到这种感觉像两种点在图上染色的问题，就可以往这边去做。如果真看不出来怎么建边，那么就根据题意，不同的条件，两个点的种类一样或者不一样，试两次。