BZOJ2916 [Poi1997]Monochromatic Triangles

每日一水。不过这题还比较有意思。最初没看清题，觉得没法数总三角形个数。

同色=总-不同色。对于一个不同色，会有两个顶点的两边颜色不同。直接按照顶点统计一下不同色的边组数，然后减一下就完了。

说好的糖果呢。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1009;

int n, m, t, c, w[maxn];

int main() {
#ifndef ONLINE_JUDGE
	//freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d", &n, &m);
	memset(w, 0, sizeof(w));
	t = n * (n - 1) * (n - 2) / 6;
	for (int i = 0; i < m; ++ i) {
		int u, v;
		scanf("%d%d", &u, &v);
		++ w[u];
		++ w[v];
	}
	c = 0;
	for (int i = 1; i <= n; ++ i)
		c += w[i] * (n - w[i] - 1);
	c >>= 1;
	printf("%d\n", t - c);
}