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();
补充：软件开发 , C语言 ,
