PKU Campus 2011

Selecting World Finals Teams on Mars I
題解：
dfs模擬
代碼： #include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

const int N = 10005;

struct Node
{
    int id;
    int s;
    friend bool operator < (const Node& _n1,const Node& _n2)
    {
        if(_n1.s == _n2.s)
            return _n1.id < _n2.id;
        return _n1.s > _n2.s;
    }
};

vector<int> graph[N];//contest info
vector<int> contest[N];//contest(i) contains team
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);
            int 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;
    if(graph[_cur].size() == 0)//leaf
    {
        vector<Node> tmp;
        Node 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;
        if(_cur != 1)
            kn = min(2,(int)tmp.size());
        else
            kn = (int)tmp.size();
        for (int i = 0; i < kn; ++i)
        {
            result[_cur].push_back(tmp[i].id);
        }
    }
    else
    {
        vector<Node> tmp;
        Node node;
        for (int i = 0; i < graph[_cur].size(); ++i)
        {
            int next = graph[_cur][i];
            if(!visited[next])
            {
                dfs(next);
                for (int j = 0; j < result[next].size(); ++j)
                {
                    node.id = result[next][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 ;
        if(_cur != 1)
            kn = min(2,(int)tmp.size());
        else
            kn = (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();