【題解】ZeroJudge d656: 11597 – Spanning Subtree

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d656
【解題想法】

  • n個節點的完全無向圖:有 n * ( n – 1) / 2 條無向邊。
  • 一棵n個節點的樹有 n – 1 條邊。
  • 因為產生的生成樹之間皆沒有共同的邊,所以最大可能的生成樹數量為 n / 2。
#include <iostream>
using namespace std;

int main() {
    int n, Case = 1;
    while (cin >> n){
        if (n == 0) break;
        cout << "Case " << Case++ << ": ";
        cout << n / 2 << "\n";
    }
    return 0;
}
分享本文 Share with friends