CF1616F Tricolor Triangles

题目描述

题目传送门

思路

发现一个边权为 $1,2,3$ 的三元环三边全部相同或不相同有一个共同的条件： 三边和为 $3$ 的倍数。

注意到这点就可以暴力把所有三元环找出来，然后根据题目要求列出方程，跑模 $3$ 意义下的高斯消元即可。

根据经典结论，三元环个数为 $\mathcal{O}(m\sqrt m)$ 的，时间复杂度为 $\mathcal{O}(m^3\sqrt m)$，能过。

代码

采用 高斯-约旦消元 实现。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 330, MAXM = 1e5;

int n, m, cnt, id;
int a[MAXM][MAXN], g[MAXN][MAXN], ans[MAXN];

void Get() {
	for (int i = id + 1; i <= cnt; i++) {
		if (a[i][m + 1]) {
			cout << -1 << "\n";
			return;
		}
	}
	for (int i = 1; i <= id; i++) {
		/*
		for (int j = i; !a[i][j]; j++) {
			ans[j] = a[i][m + 1];
		}
		*/
		int p = i;
		while (!a[i][p]) p++;
		ans[p] = a[i][m + 1];
	}

	for (int i = 1; i <= m; i++) cout << (ans[i] ? ans[i] : 3) << " ";
	cout << endl;
}


void solve() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		static int u, v, w;
		cin >> u >> v >> w;
		if (w != -1) {
			cnt++;
			a[cnt][i] = 1;
			a[cnt][m + 1] = w % 3;
		}
		g[u][v] = g[v][u] = i;
	}
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			for (int k = j + 1; k <= n; k++)
				if (g[i][j] && g[j][k] && g[k][i]) {
					cnt++;
					a[cnt][g[i][j]] = a[cnt][g[j][k]] = a[cnt][g[k][i]] = 1;
				}
	for (int i = 1; i <= m; i++) {
		int now = 0;
		for (int j = id + 1; j <= cnt; j++) 
			if (a[j][i])
				now = j;
		if (!now) {
			ans[i] = 0;
			continue;
		}
		swap(a[++id], a[now]);
		if (a[id][i] != 1) for (int j = i; j <= m + 1; j++) a[id][j] = 3 - a[id][j];
		for (int j = 1; j <= cnt; j++) {
			if (id != j && a[j][i]) {
				int x = a[j][i];
				for (int k = i; k <= m + 1; k++) 
					a[j][k] = (a[j][k] - x * a[id][k] + 9) % 3;
			}
		}
	}
	Get();
	return;
}

void clear() {
	memset(g, 0, sizeof g);
	memset(a, 0, sizeof a);
	cnt = id = 0;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int _;
	cin >> _;
	while (_--) {
		clear();
		solve();
	}
	return 0;
}