记录编号	578523	评测结果	WAAAAWAWWW
题目名称	[SCOI2011] 糖果	最终得分	50
用户昵称	zxhhh	是否通过	未通过
代码语言	C++	运行时间	0.203 s
提交时间	2023-03-24 18:41:45	内存使用	9.35 MiB

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;
typedef long long ll;
int n, k;
int dfn[N], low[N], scc_idx[N], scc_cnt, dfs_t, scc_siz[N], d[N], m[N], instk[N];
int stk[N], ed;
int ver[N<<2], nxt[N<<2], hd1[N], hd2[N], opt[N<<2], eidx = 1;

struct edge {
	int x, y, op;
	bool friend operator < (const edge & a, const edge & b) {
		if (a.x != b.x) return a.x < b.x;
		if (a.y != b.y) return a.y < b.y;
		return a.op < b.op;
	}
	bool friend operator != (const edge & a, const edge & b) {
		return a.x != b.x || a.y != b.y || a.op != b.op;
	}
}edges[N<<2];

void add (int x, int y, int op, int hd[]) {
	ver[++eidx] = y;
	opt[eidx] = op;
	nxt[eidx] = hd[x];
	hd[x] = eidx;
}

void tarjan (int x) {
	dfn[x] = low[x] = ++dfs_t; stk[ed++] = x; instk[x] = 1;
	for (int i = hd1[x]; i ;i = nxt[i]) {
		int y = ver[i];
		if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
		else if (instk[y]) low[x] = min(low[x], dfn[y]);
	}
	if (low[x] == dfn[x]) {
		int tmp = -1; scc_cnt++;
		do {
			tmp = stk[--ed];
			instk[tmp] = 0;
			scc_idx[tmp] = scc_cnt;
			scc_siz[scc_cnt]++;
		} while (tmp != x);
	}
}

ll merge () {
	int ecnt = 0; ll ans = 0;
	for (int i = 1;i <= n;i++) {
		for (int j = hd1[i]; j ;j = nxt[j]) {
			int y = ver[j];
			if (scc_idx[y] == scc_idx[i] && !opt[j]) return -1;
			int tx = scc_idx[i], ty = scc_idx[y];
			if (tx != ty) edges[++ecnt] = (edge){tx, ty, opt[j]};
		}
	}
	sort (edges+1, edges+1+ecnt);
	eidx = 0;
	queue <int> q;
	for (int i = 1;i <= ecnt;i++) if (edges[i] != edges[i-1]) add(edges[i].x, edges[i].y, edges[i].op, hd2), d[edges[i].y]++;
	for (int i = 1;i <= scc_cnt;i++) if (!d[i]) q.push(i), m[i] = 1;
	while (q.size()) {
		int t = q.front(); q.pop();
		ans += (ll)m[t]*scc_siz[t];
		for (int i = hd2[t]; i ;i = nxt[i]) {
			int y = ver[i];
			d[y]--;
			if (opt[i]) m[y] = max(m[y], m[t]);
			else m[y] = max(m[y], m[t]+1);
			if (!d[y]) q.push(y);
		}
	}
	return ans;
}

int main () {
	freopen("tangguo.in", "r", stdin);
	freopen("tangguo.out", "w", stdout);
	scanf("%d%d", &n, &k);
	while (k--) {
		int x, a, b, op;
		scanf("%d%d%d", &x, &a, &b);
		if (a == b) {
			if (x&1) continue;
			else {
				printf("-1\n");
				return 0;
			}
		}  
		if (x == 1) {
			add(a, b, 1, hd1); add(b, a, 1, hd1);
			continue;
		}
		if (x&1) swap(a, b);
		op = x&1;
		add(a, b, op, hd1);
	}
	for (int i = 1;i <= n;i++) if (!dfn[i]) tarjan(i);
	printf("%lld\n", merge());
	return 0;
}