程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> codeforces 547D Mike and Fish 歐拉路徑

codeforces 547D Mike and Fish 歐拉路徑

編輯：關於C++

題意：

給定二維平面上的n個點的坐標

問：

把每個點用紅色或藍色染色，使得水平共線（或者垂直共線）的點中紅色與藍色數量差不超過1.

思路：

我們建一個二部圖，X集是x軸，Y集是y軸

那麼點(1,5)就是 x集的 1向 y集的 5連一條邊。

此時點就是用邊來表示的，那我們的任務就是給邊染色。

使得：

對於二部圖中任意一個點，點所連接的紅邊和藍邊數量差不超過1.

那麼我們可以認為這個點的入邊就是紅色，出邊就是藍色。顯然這就是一個歐拉路徑。

所以爆搜歐拉路徑即可。

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template 
inline bool rd(T &ret) {
	char c; int sgn;
	if (c = getchar(), c == EOF) return 0;
	while (c != '-' && (c<'0' || c>'9')) c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
	ret *= sgn;
	return 1;
}
template 
inline void pt(T x) {
	if (x <0) {
		putchar('-');
		x = -x;
	}
	if (x>9) pt(x / 10);
	putchar(x % 10 + '0');
}
const int N = 2e5 + 10;
typedef long long ll;
struct Edge{
	int from, to, col, nex;
}edge[N << 2];
int head[N<<1], edgenum;
void add(int u, int v){
	Edge E = { u, v, -1, head[u] };
	edge[edgenum] = E;
	head[u] = edgenum++;
}
int n;
int vis[N << 2];
int du[N << 2];
void dfs(int u){
//	printf("%d ", u);
	for (int i = head[u]; ~i; i = head[u] = edge[i].nex){
		if (edge[i].col != -1)continue;
		int v = edge[i].to;
		edge[i].col = u < v;
		edge[i ^ 1].col = -2;
		vis[u]++; vis[v]++;
		dfs(v);
		break;
	}
}
vectorX, Y;
int x[N], y[N];
int main(){
	rd(n);
	memset(head, -1, sizeof head); edgenum = 0;
	for (int i = 1; i <= n; i++){
		rd(x[i]); rd(y[i]);
		X.push_back(x[i]); 
		Y.push_back(y[i]);
	}
	sort(X.begin(), X.end());
	sort(Y.begin(), Y.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	Y.erase(unique(Y.begin(), Y.end()), Y.end());
	for (int i = 1; i <= n; i++){
		x[i] = lower_bound(X.begin(), X.end(), x[i]) - X.begin() ;
		y[i] = lower_bound(Y.begin(), Y.end(), y[i]) - Y.begin()  + n;
		du[x[i]]++; du[y[i]]++;
		add(x[i], y[i]); add(y[i], x[i]);
	}
//	for (int i = 0; i <= 2 * n; i++)printf("(%d,%d)\n", i, du[i]); 

	for (int i = 0; i <= 2 * n; i++)
	if (du[i] & 1 && vis[i] < du[i]){
//		printf("odd dfs %d: ", i);
		dfs(i);
//		puts("");
	}
	for (int i = 0; i <= 2 * n; i++)
	if (du[i] && vis[i] < du[i]){
	//	printf("normal dfs %d: ", i);
		dfs(i);
//		puts("");
	}
	for (int i = 0; i < edgenum; i ++)
	if (edge[i].col >= 0)
		putchar(edge[i].col ? 'r' : 'b');
	return 0;
}
/*
4
1 1
1 2
2 1
2 2

7
1 0
2 0
2 1
0 2
1 2
2 2
2 3



*/