Codeforces 229C Triangles
题目意思是说Alice和Bob玩一个新的游戏（似乎这两人经常在博弈题目里见到）
首先Alice给定一个无向完全图，然后从中保留下m条边，其余的边放到另外一个平面上。
这样就有两个无向图。问这两个图有多少个三角形。（不是严格意义上的三角形，只要有三条边构成的闭合图形就可以）
第一个样例，从顶点，然后逆时针编号为1-N；红色部分是留下的m条边
从图中可以看出构成的三角形只有3个，红色两个，黑色一个
如果是无向完全图，那么三角形的个数就是C（n，3），从N个顶点任选3个顶点就行。
现在拆分成两个图，直接数三角形的个数不太现实。
那就逆向思维，用总数减去被破坏的三角形。
完全无向图中，每个顶点都有n-1条边。现在每个顶点的边分为两部分，红色和黑色部分。
红色和黑色部分不再一个平面内，所以在红色部分选一条边，在黑色部分选一条边，第三条边任选，这样形成的三角形一定是被破坏的。
第三条边的种类无所谓，这类三角形至少有一条边与另外两条边不再一个平面，于是拆分为两个平面以后这个三角形就被破坏。所以每个顶点破坏三角形的个数为C（红，1）*C（黑，1）
每个顶点都这样操作，就统计出所有被破坏的三角形。
但是这样，每个被破坏的三角形都统计了两次。就拿上面的例子说，以1为顶点的时候破坏了三角形124，以4为顶点的时候破坏了三角形412.这两个三角形是一样的。
首先Alice给定一个无向完全图，然后从中保留下m条边，其余的边放到另外一个平面上。
这样就有两个无向图。问这两个图有多少个三角形。（不是严格意义上的三角形，只要有三条边构成的闭合图形就可以）
第一个样例，从顶点，然后逆时针编号为1-N；红色部分是留下的m条边
从图中可以看出构成的三角形只有3个，红色两个，黑色一个
如果是无向完全图，那么三角形的个数就是C（n，3），从N个顶点任选3个顶点就行。
现在拆分成两个图，直接数三角形的个数不太现实。
那就逆向思维，用总数减去被破坏的三角形。
完全无向图中，每个顶点都有n-1条边。现在每个顶点的边分为两部分，红色和黑色部分。
红色和黑色部分不再一个平面内，所以在红色部分选一条边，在黑色部分选一条边，第三条边任选，这样形成的三角形一定是被破坏的。
第三条边的种类无所谓，这类三角形至少有一条边与另外两条边不再一个平面，于是拆分为两个平面以后这个三角形就被破坏。所以每个顶点破坏三角形的个数为C（红，1）*C（黑，1）
每个顶点都这样操作，就统计出所有被破坏的三角形。
但是这样，每个被破坏的三角形都统计了两次。就拿上面的例子说，以1为顶点的时候破坏了三角形124，以4为顶点的时候破坏了三角形412.这两个三角形是一样的。
所以最后的答案就是三角形总数减去每个顶点破坏三角形总和的一半。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long n,m,sum,des,x,y;
long long d[1000006];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
sum=des=0;
memset(d,0,sizeof(d));
sum=(n-2)*(n-1)*n/6;//三角形总数
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
d[x]++;//统计每个顶点红色边的条数
d[y]++;
}
for(int i=1;i<=n;i++)
des=des+d[i]*(n-1-d[i]);//每个顶点破坏三角形的个数
des=des/2;
printf("%I64d\n",sum-des);
}
}
投递旷视等公司10个岗位 >
哔哩哔哩公司氛围 91人发布