【luogu P8326】Fliper (Graph Theory) (Construction) (Eulerian Circuit)

Fliper

题目链接：luogu P8326

题目大意

平面上有 n 个挡板（Top left to bottom right and top right to bottom left）,If the ball touches it will 90 change the trajectory.
Then you want to give each baffle a color,Makes a bounce sequence for each loop,The number of baffles that satisfy each color is the same and an even number.（If a baffle appears twice in the sequence it counts twice）
If the scheme output cannot be constructed -1.

思路

First consider finding the loop.
That is to split a baffle into two points（两面）,Then, along with an edge of the same color, the color of this edge determines the color of the baffle.
Then you connect the two points of a face that bounce from one face back to one place,Then shrink this a bit.

That would make some big points（Represents a cyclic sequence）,and some other points（not in a circular sequence）,Then we connect it to one $\inf$ 点.

Then consider dyeing,You will find that you have to satisfy all the looping sequences,If brute force can solve the equation but the complexity is too large.
Consider finding some character,Then this is a graph, let's look for the properties of graph theory.

When we find a solution, let's see what happens,It is not difficult to think of the situation where the degree of each large point should be $8$ 的倍数.
Then there is a property in graph theory that there is always an even number of points with an odd degree.
Then we can get that $\inf$ The degree of the point must also be even.（If it is an odd number then only $1$ 个点,不是偶数个）
It's not hard to think of something called an Euler circuit.
Consider finding Euler circuits and then coloring them in black and white,Then we have two colors.

It is not difficult to come up with four approaches：Because after this the degree is $4$ 的倍数,So there is also an Euler circuit.（According to the above graph theory properties, there will also be $\inf$ The number of points is an even number）
Then we will run another Euler circuit for the two separated color maps,It's divided into four.

代码

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

using namespace std;

const int N = 5e5 + 1000; 
/* op=0: / , op=1: \ */
/* i / n+i i \ n+i */
struct node {
    
	int x, y, op, id;
}a[N];
int n, col[N * 2], tot;
int ans[N], KK_, sta[N * 2], du[N * 2];
vector <int> G[N * 2], F[N * 2], F_[N * 2];
bool in[N * 2], use[N * 2];

int zf, re; char c;
int read() {
    
	zf = 1; re = 0; c = getchar();
	while (c < '0' || c > '9') {
    
		if (c == '-') zf = -zf;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
    
		re = (re << 3) + (re << 1) + c - '0';
		c = getchar();
	}
	return re * zf;
}

bool cmpx(node x, node y) {
    if (x.x != y.x) return x.x < y.x; return x.y < y.y;}
bool cmpy(node x, node y) {
    if (x.y != y.y) return x.y < y.y; return x.x < y.x;}

void add(int x, int y) {
    
	G[x].push_back(y); G[y].push_back(x);
}
//0:light edge
//1:same color edge
//2:INF边 

bool Find;
void dfs(int now, int father) {
    
	sta[++sta[0]] = now; in[now] = 1;
	for (int i = 0; i < G[now].size(); i++)
		if (G[now][i] != father) {
    
			if (in[G[now][i]]) {
    
				tot++; Find = 1;
				while (sta[0]) col[sta[sta[0]]] = tot, sta[0]--;
				return ;
			}
			else dfs(G[now][i], now);
			if (Find) return ;
		}
}

void Add(int x, int y, int z) {
    
	F[x].push_back(y); if (x != y) F[y].push_back(x); 
	F_[x].push_back(z); if (x != y) F_[y].push_back(z);
	du[x]++; du[y]++;
}

void Link() {
    
	sort(a + 1, a + n + 1, cmpy);
	for (int L = 1, R; L <= n; L = R + 1) {
    
		R = L; while (R < n && a[R + 1].y == a[L].y) R++;
		for (int i = L; i < R; i++) {
    
			add(n + a[i].id, a[i + 1].id);
		}
	}
	sort(a + 1, a + n + 1, cmpx);
	for (int L = 1, R; L <= n; L = R + 1) {
    
		R = L; while (R < n && a[R + 1].x == a[L].x) R++;
		for (int i = L; i < R; i++) {
    
			if (a[i].op == 0 && a[i + 1].op == 0) add(a[i].id, n + a[i + 1].id);
			if (a[i].op == 0 && a[i + 1].op == 1) add(a[i].id, a[i + 1].id);
			if (a[i].op == 1 && a[i + 1].op == 0) add(n + a[i].id, n + a[i + 1].id);
			if (a[i].op == 1 && a[i + 1].op == 1) add(n + a[i].id, a[i + 1].id);
		}
	}
	
	for (int i = 1; i <= 2 * n; i++)
		if (!in[i]) {
    
			sta[0] = 0, Find = 0, dfs(i, 0);
			if (!Find) {
    
				while (sta[0]) use[sta[sta[0]]] = 1, sta[0]--;
			}
		}
	
	for (int i = 1; i <= n; i++) {
    
		int x = use[i] ? 2 * n + 1 : col[i];
		int y = use[n + i] ? 2 * n + 1 : col[n + i];
		Add(x, y, i);
	}
}

bool check_ans() {
    
	for (int i = 1; i <= tot; i++)
		if (du[i] % 8 != 0) return 0;
	return 1;
}

struct nde {
    
	int id, to, nxt;
}e[N * 2];
int in_[N * 2], le[N * 2], KK;

void run_way(int now) {
    
	for (int i = le[now]; i; i = le[now]) {
    
		le[now] = e[i].nxt;
		if (in_[e[i].id]) continue; in_[e[i].id] = 1;
		run_way(e[i].to); sta[++sta[0]] = e[i].id;
	}
}

void get_oula() {
    
	memset(in_, 0, sizeof(in_)); sta[0] = 0;
	run_way(2 * n + 1);
	for (int i = 1; i <= tot; i++) run_way(i);
	for (int i = 1; i <= sta[0]; i += 2)
		in_[sta[i]]++;
}

void clear() {
    
	KK = 0; memset(le, 0, sizeof(le));
}

void slove() {
    
	clear();
	for (int i = 1; i <= 2 * n + 1; i++)
		for (int j = 0; j < F[i].size(); j++)
			e[++KK] = (nde){
    F_[i][j], F[i][j], le[i]}, le[i] = KK;
	get_oula();
	for (int i = 1; i <= n; i++) ans[i] = in_[i] * 2;
	
	clear();
	for (int i = 1; i <= 2 * n + 1; i++)
		for (int j = 0; j < F[i].size(); j++)
			if (ans[F_[i][j]] == 2)
				e[++KK] = (nde){
    F_[i][j], F[i][j], le[i]}, le[i] = KK;
	get_oula();
	for (int i = 1; i <= n; i++) if (in_[i]) ans[i] += in_[i] - 2;
	clear();
	for (int i = 1; i <= 2 * n + 1; i++)
		for (int j = 0; j < F[i].size(); j++)
			if (ans[F_[i][j]] == 4)
				e[++KK] = (nde){
    F_[i][j], F[i][j], le[i]}, le[i] = KK;
	get_oula();
	for (int i = 1; i <= n; i++) if (in_[i]) ans[i] += in_[i] - 2;
	
	for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
}

int main() {
    
// freopen("pinball.in", "r", stdin);
// freopen("pinball.out", "w", stdout);
	
	n = read();
	for (int i = 1; i <= n; i++) {
    
		a[i].x = read(); a[i].y = read(); a[i].id = i;
		char c = getchar(); while (c != '\\' && c != '/') c = getchar();
		if (c == '/') a[i].op = 0; else a[i].op = 1;
	}
	
	Link();
	if (!check_ans()) {
    printf("-1"); return 0;}
	slove();
	
	return 0;
}