題意:?
? ? ? ? http://codeforces.com/problemset/problem/229/C
? ? ? ? 給你一個(gè)全圖,分成兩部分,問(wèn)你這兩個(gè)途中一共有多少個(gè)三角形.


思路:
? ? ? 如果是一個(gè)完整的全圖,那么三角形的個(gè)數(shù)就是 C(n中取3),那么答案就是C(n中取3)減去被破壞的三角形個(gè)數(shù),這個(gè)題目關(guān)鍵的一點(diǎn)就是全圖,全圖中的每一個(gè)點(diǎn)的度數(shù)都是n-1,那么在其中的一個(gè)圖中的度數(shù)是 a的話,另一個(gè)圖中的度數(shù)就是 n - 1 - a,而每一個(gè)圖中點(diǎn)的度數(shù)就是他的邊數(shù),想像一下吧兩個(gè)圖組合到一起的話就一定會(huì)另外形成 a * (n - 1 - a)個(gè)三角形,因?yàn)榧偃缫粋€(gè)點(diǎn)連出去兩條邊(這兩條邊在兩個(gè)圖中),而那兩條邊又一定會(huì)被一條邊相連接(因?yàn)槭侨珗D),就這樣根據(jù)給的圖就可以算出每一個(gè)點(diǎn)所在被破壞三角形的個(gè)數(shù),需要注意一點(diǎn)的就是每一個(gè)破壞的三角形肯定是一條邊在一個(gè)集合,而另兩條邊在另一個(gè)集合,那么這個(gè)破壞的三角形的三個(gè)點(diǎn)就一定是有兩個(gè)點(diǎn)既在圖1中有邊,也在圖二中有邊,所以算了兩次,所以要把所有被破壞的三角形個(gè)數(shù)除以二,在用總的個(gè)數(shù)減去破壞的個(gè)數(shù)就是答案..
? ? ??
? ? ??

#include<stdio.h>
#include<string.h>


#define N ?1000000 + 1000


__int64 deg[N];


int main ()
{
? ?int n ,m ,i ,a ,b;
? ?__int64 sum ,s;
? ?while(~scanf("%d %d" ,&n ,&m))
? ?{
? ? ? memset(deg ,0 ,sizeof(deg));
? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? {
? ? ? ? ?scanf("%d %d" ,&a ,&b);
? ? ? ? ?deg[a] ++ ,deg[b] ++;
? ? ? }
? ? ? __int64 nn = n;
? ? ? sum = 0; ??
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?sum += deg[i] * (nn - 1 - deg[i]);
? ? ? }?
? ? ? printf("%I64d\n" ,nn * (nn - 1) * (nn - 2) / 6 - sum / 2);
? ?}
? ?return 0;
}

總結(jié)

以上是生活随笔為你收集整理的codeforces 229C的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。