POI 1997 單色三角形 Monochromatic triangles
本文正體字版由OpenCC轉換
O(N^3)的枚舉是無法忍受的，這道題可以從反面考慮。單色三角形的個數就是全部的三角形的個數減去不同色三角形的個數。
在一個不同色的三角形中，顯然有兩個頂點，每個頂點連着這個三角形內的不同顏色的兩條邊。一個頂點出發有N-1條邊，如果頂點i連接着D[i]條紅邊，那麼它一定連接着(N-1-D[i])條黑邊，這個頂點在D[i](N-1-D[i])個不同色三角形內。而一個頂點在一個三角形內被計算了兩次，所以整個圖中一共有 Sum{ D[i](N-1-D[i])/2 | i=1..N }個不同色三角形。
由於一共有C(N,3)個三角形，所以結果就是
C(N,3) - Sum{ D[i]*(N-1-D[i])/2 | i=1..N }
/*
* Problem: POI1997 tro
* Author: Guo Jiabao
* Time: 2008.11.28 19:45:22
* State: Solved
*/
#include <iostream>
#include <stdio.h>
using namespace std;
const int MAX=1001;
int D[MAX];
int N,M,Ans;
void init()
{
int i,a;
freopen("tro.in","r",stdin);
freopen("tro.out","w",stdout);
scanf("%d%d",&N,&M);
for (i=1;i<=M*2;i++)
{
scanf("%d",&a);
D[a]++;
}
}
void solve()
{
int i,T,S,A;
T=N*(N-1)*(N-2)/6;
S=0;
for (i=1;i<=N;i++)
{
A=D[i]*(N-1-D[i]);
S+=A/2;
}
Ans=T-S;
}
int main()
{
init();
solve();
cout << Ans;
return 0;
}
單色三角形
在空間中給出了n個點。這些點任三點不共線，並且每兩個點之間都有一條線相連，每一條線不是紅的就是黑的。在這些點和線組成的三角形中，如果一個三角形的三條邊的顏色都相同，那麼我們就稱這個三角形爲單色三角形。現給出所有塗紅色的線，試求出單色三角形的數目。
任務：
請寫一個程序：
從文本文件中讀入點數和對紅色連線的描述；
找出該圖中紅色三角形的數目；
把結果輸出到文件TRO.OUT中。
輸入格式：
在文本文件TRO.IN的第一行包括一個整數n，3 <= n <= 1000，爲空間中的點數。
該文件的第二行爲一個整數m，0 <= m <= 250000，爲紅色連線的數目。
以下的m行中每行爲兩個用空格分開的整數p和k，1 <= p < k <= n，表示第p點和第k號點之間的連線爲紅色。
輸出格式：
你應該在文本文件TRO.OUT輸出唯一的一個整數——同色三角形的數目。
樣例：
輸入
6
9
1 2
2 3
2 5
1 4
1 6
3 4
4 5
5 6
3 6
輸出
2
上次修改時間 2017-02-03