Codeforces Round #142 (Div. 1) C. Triangles

题意：http://mp.weixin.qq.com/s/G2mjArjpgp7Ihd3k_WS_Lw

题解：http://mp.weixin.qq.com/s/ITNKOywnVn0QDC-hYYl_5Q

补充：规律？公式？有点想不通。。。只能尝试简单理解。

   答案 = 

   首先，上式只能用于完全图。前半部分就是组合，从n个点中选3个点组成一个三角形，后半部分为每个点红边数乘以蓝边数之和除以2。

   主要是后半部分的理解，红边乘以蓝边可以理解为一个点引出的红边和蓝边的组合。对于一个三角形若三边为同一种颜色，则必定不会被去掉，若红蓝比例为1：2或者2：1，则该三角形会被选中两次，也就是去掉两次，所以累加之后要除以2。。。 = =

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1000005; int deg[N]; int main() { int n, m, u, v; scanf("%d%d", &n, &m); LL org = 1LL * n * (n - 1) * (n - 2) / 6; for(int i = 0; i < m; i++) { scanf("%d%d", &u, &v); deg[u]++; deg[v]++; } LL tmp = 0; for(int i = 1; i <= n; i++) { tmp += 1LL * deg[i] * (n - 1 - deg[i]); } printf("%I64d\n", org - tmp / 2); return 0; }