Jzoj p4672 graph coloring

Main idea:

An undirected graph with n nodes and m edges.
Initially, each edge is blue or red.
Each time you can color all the edges of a node connection (from red to blue, blue to red).
Find a scheme with the least steps to make all edges the same color.

1&lt;=n,m&lt;=1000001&lt;=n,m&lt;=1000001<=n,m<=100000
Edge without self loop

Analysis:

Change the edge to blue or red respectively, and then take the optimal scheme
Because each point can be changed at most once, and changing twice is equal to no change.
So we want to divide the points into two sets, S and T, which represent the points to be changed and the points not to be changed.
Then it's similar to the idea of 2 − SAT2-SAT2 − SAT,
If we want to turn all the edges red now, let's say that there is a red edge between u and v. If you want to maintain this color, u and v belong to the same
Set (S or T). On the other hand, if this edge is blue, then u and v must be in two different sets.
So the problem is simplified to 0-1 graph coloring problem, which can be solved by dfs. Note that graphs are not necessarily connected.

Code:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <algorithm>

#define N 100005

using namespace std;

struct Node {
	int To, nxt, col;
}e[N*2];
int use[N], tot[2], ls[N], n, m, cnt, usecol;
bool check;

void Addedge(int u, int v, int w)
{
    e[++cnt].To = v, e[cnt].col = w, e[cnt].nxt = ls[u], ls[u] = cnt;
    e[++cnt].To = u, e[cnt].col = w, e[cnt].nxt = ls[v], ls[v] = cnt;
}

void dfs(int x)
{
	if (!check) return;
	tot[use[x]]++; 
	for (int i = ls[x]; i; i = e[i].nxt)
	{
		int now = e[i].col ^ use[x] ^ usecol;
		if (use[e[i].To] == -1)
		{
			use[e[i].To] = now;
			dfs(e[i].To);
			if (!check) return;
		} else if (use[e[i].To] != now) { check = 0; return; }
	}
}

// Red 1 Blue 0
 
int main()
{
	scanf("%d %d", &n, &m);
	int u, v; char w;
	for (int i = 1; i <= m; i++) 
	{
	    scanf("%d %d %c", &u, &v, &w);
		Addedge(u, v, (w == 'R'));
    }
    
    int ans1 = 0;
	memset(use, 255, sizeof(use)); usecol = 1; check = 1;
	for(int i = 1; i <= n; i++)
		if (use[i] == -1)
		{
			tot[1] = tot[0] = 0; use[i] = 1;
			dfs(i);
			ans1 += min(tot[0], tot[1]);
			if (!check) { ans1 = -1; break; } 
		}
	
	int ans2 = 0;
	memset(use, 255, sizeof(use)); usecol = 0; check = 1;
	for(int i = 1; i <= n; i++)
		if (use[i] == -1)
		{
			tot[1] = tot[0] = 0; use[i] = 1;
			dfs(i);
			ans2 += min(tot[0], tot[1]);
			if (!check) 
			{ 
			   if (ans1 == -1) printf("-1\n"); else printf("%d\n", ans1);
			   return 0;   
		    }
		}
	if (ans1 == -1) printf("%d\n", ans2); else printf("%d\n", min(ans1, ans2));
	return 0;
}

Posted on Tue, 03 Dec 2019 05:21:56 -0800 by powergen