C++(clang++11) 解法, 执行用时: 23ms, 内存消耗: 6648K, 提交时间: 2021-03-25 14:38:31

#include <iostream>
#include <cstdio>
#include <queue>
#define ll long long

using namespace std;

int head[400010], cnt, N, dis[400010];
bool in[400010];

struct node {
	int v, w, next;
} e[400005];

inline void add (int u, int v, int w) {
	e[++cnt].v = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}


inline bool spfa (int u) {
	in[u] = true;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v, w = e[i].w;
		if (dis[v] < dis[u] + w) {
			dis[v] = dis[u] + w;
			if (in[v] || !spfa (v)) return false;
		}
	}
	in[u] = false;
	return true;
}

inline int read () {
	int x = 0, f = 1;
	char ch = getchar ();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f *= -1;
		ch = getchar ();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar ();
	}
	return x * f;
}

int main () {
	int K, X, A, B;
	bool flag = false;
	N = read ();
	K = read ();
	for (int i = 1; i <= K; i++) {
		X = read (), A = read (), B = read ();
		if (X == 1) {
			add (A, B, 0);
			add (B, A, 0);
		} 
		else if (X == 2) {
			add (A, B, 1);
			if (A == B) {
				printf ("-1");
				return 0;
			}
		}
		else if (X == 3) add (B, A, 0);
		else if (X == 4) {
			add (B, A, 1);
			if (A == B) {
				printf ("-1");
				return 0;
			}
		}
		else add (A, B, 0);
	}
	for (int i = N; i >= 1; i--) add (N + 1, i, 1);
	if (!spfa (N + 1)) printf ("-1");
	else {
		ll ans = 0;
		for (int i = 1; i <= N; i++) ans += dis[i];
		printf ("%lld", ans);
	}
	return 0;
}