PKU Campus 2011 選拔賽：火星世界總決賽隊伍選拔 I (DFS 模擬)

題目背景

PKU Campus 2011 選拔賽題目《Selecting World Finals Teams on Mars I》。

解法：DFS 模擬

樹形結構模擬比賽過程，葉子節點為隊伍，內部節點為比賽場次。自底向上合併，按分數排序取前 2 名（根節點取所有），最終輸出根節點獲勝隊伍名稱。

核心代碼

#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

const int N = 10005;

struct Node {
    int id, s;
    friend bool operator<(const Node& a, const Node& b) {
        if (a.s == b.s) return a.id < b.id;
        return a.s > b.s; // 分數降序
    }
};

vector<int> graph[N];    // 比賽場次連接關係
vector<int> contest[N]; // 場次包含的隊伍
vector<int> result[N];  // 場次獲勝隊伍
string name[5005];
int s[5005];
bool visited[N];
int n, m;

void init() {
    for (int i = 1; i <= n; ++i) {
        graph[i].clear(); contest[i].clear(); result[i].clear();
    }
    memset(visited, 0, sizeof(visited));
}

void input() {
    int x, y;
    for (int i = 0; i < n + m - 1; ++i) {
        scanf("%d %d", &x, &y);
        if (x <= n && y <= n) { // 場次-場次連接
            graph[x].push_back(y);
            graph[y].push_back(x);
        } else { // 場次-隊伍關係
            int kx = min(x, y), ky = max(x, y);
            contest[kx].push_back(ky - n);
        }
    }
    char buf[300]; int k;
    for (int i = 1; i <= m; ++i) {
        scanf("%s %d", buf, &k);
        name[i] = string(buf);
        s[i] = k;
    }
}

void dfs(int cur) {
    visited[cur] = true;
    vector<Node> tmp;
    Node node;

    if (graph[cur].empty()) { // 葉子場次：直接包含隊伍
        for (int i = 0; i < contest[cur].size(); ++i) {
            node.id = contest[cur][i];
            node.s = s[node.id];
            tmp.push_back(node);
        }
    } else { // 內部場次：合併子場次結果 + 本場次隊伍
        for (int i = 0; i < graph[cur].size(); ++i) {
            int nxt = graph[cur][i];
            if (!visited[nxt]) {
                dfs(nxt);
                for (int j = 0; j < result[nxt].size(); ++j) {
                    node.id = result[nxt][j];
                    node.s = s[node.id];
                    tmp.push_back(node);
                }
            }
        }
        for (int i = 0; i < contest[cur].size(); ++i) {
            node.id = contest[cur][i];
            node.s = s[node.id];
            tmp.push_back(node);
        }
    }

    sort(tmp.begin(), tmp.end());
    int kn = (cur == 1) ? tmp.size() : min(2, (int)tmp.size());
    for (int i = 0; i < kn; ++i) result[cur].push_back(tmp[i].id);
}

void Test() {
    init(); input(); dfs(1);
    vector<Node> tmp; Node node;
    for (int i = 0; i < result[1].size(); ++i) {
        node.id = result[1][i]; node.s = s[node.id]; tmp.push_back(node);
    }
    sort(tmp.begin(), tmp.end());
    for (int i = 0; i < tmp.size(); ++i) printf("%s ", name[tmp[i].id].c_str());
}

int main() {
    // freopen("data.txt","r",stdin);
    while (scanf("%d %d", &n, &m) != EOF) Test();
    return 0;
}

關鍵點

• 圖建模：場次為節點，邊連接場次或場次-隊伍。
• DFS 後序遍歷，子場次結果上傳合併。
• 排序規則：分數降序，分數相同 ID 升序。
• 根節點 (1) 取所有獲勝隊伍，其餘取前 2 名。