a858: 數三角形

2021-07-03 16:22:14 +0800 CST Tags: math

出處：https://zerojudge.tw/ShowProblem?problemid=a858
提交：https://zerojudge.tw/Submissions?problemid=a858&account=allllllan123456

問題：給定一張頂點數 $N\in[3,1000]$ 的無向完全圖，其中每條邊只可能是紅色或黑色。完全圖保證任三個相異點都能形成一個三角形，那麼請問三邊同色的三角形有幾個？如果可以在 $\mathcal O(N^2)$ 時間內計算完畢為佳。

解法：看到這個時間要求，幾乎可以確定沒辦法一個一個三角形去計算，但是如果把同色的邊合成一個數字來統計，可能就會比較快喔。考慮與某個特定頂點相接的所有邊，它們都可以被分成紅色或黑色兩類，如果我們任抓兩個同色邊出來，其實仍然無法保證它們所夾的第三條邊也同色，這樣子並無法計算同色三角形的數量；神奇的是，如果我們任抓兩個異色邊出來，竟然不用檢查所夾的第三條邊就能保證此三角形為異色三角形，由此可見計算異色三角形真的比較簡單呢！對於每個異色三角形 ABC，如果 A 點所夾的兩條邊異色，那麼勢必 B 或 C 其中一點所夾的兩條邊也是異色，因此在統計每個頂點觸及到幾個異色三角形的時候，同一個異色三角形會被算到兩次 (因為有兩個頂點它們各自所夾的兩條邊是異色)，於是全部異色三角形的數量就是 $\displaystyle\frac12\cdot\sum_{v\ \in\ V}r_v\cdot b_v$，其中 $r_v$ 是與 $v$ 這個點所接的紅色邊數量，$b_v$ 是與 $v$ 這個點所接的黑色邊數量，最後再從全部的三角形數量 $C(N,3)$ 去扣除即可。

附註：
[1] https://zerojudge.tw/ShowThread?postid=13146&reply=0

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
 5    int sum = 0, n; cin >> n;
 6    for (int i=0; i<n; i++) {
 7        int num[3] = {0};
 8        for (int j=0, t; j<n; j++)
 9            cin >> t, num[t]++;
10        sum += num[1] * num[2];
11    }
12    sum /= 2;
13    cout << (long long)n*(n-1)*(n-2)/6 - sum << '\n';
14    return 0;
15}