BZOJ2916 [Poi1997]Monochromatic Triangles

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

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

说好的糖果呢。

1	#include <cstdio>
2	#include <cstring>
3	#include <algorithm>
4	
5	using namespace std;
6	
7	const int maxn = 1009;
8	
9	int n, m, t, c, w[maxn];
10	
11	int main() {
12	#ifndef ONLINE_JUDGE
13		//freopen("in.txt", "r", stdin);
14	#endif
15	
16		scanf("%d%d", &n, &m);
17		memset(w, 0, sizeof(w));
18		t = n * (n - 1) * (n - 2) / 6;
19		for (int i = 0; i < m; ++ i) {
20			int u, v;
21			scanf("%d%d", &u, &v);
22			++ w[u];
23			++ w[v];
24		}
25		c = 0;
26		for (int i = 1; i <= n; ++ i)
27			c += w[i] * (n - w[i] - 1);
28		c >>= 1;
29		printf("%d\n", t - c);
30	}
31