浙江财经大学
信息管理与工程学院

ACDream 1015 Double Kings

本文由 Ocrosoft 于 2016-08-18 14:10:22 发表

Double Kings

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

Our country is tree-like structure, that is to say that N cities is connected by exactly N – 1 roads.
The old king has two little sons. To make everything fairly, he dicided to divide the country into two parts and each son get one part. Two sons can choose one city as their capitals. For each city, who will be their king is all depend on whose capital is more close to them. If two capitals have the same distance to them, they will choose the elder son as their king. 
(The distance is the number of roads between two city)
The old king like his elder son more, so the elder son could choose his capital firstly. Everybody is selfish, the elder son want to own more cities after the little son choose capital while the little son also want to own the cities as much as he can.
If two sons both use optimal strategy, we wonder how many cities will choose elder son as their king.

Input

There are multiple test cases.
The first line contains an integer N (1 ≤ N ≤ 50000).
The next N – 1 lines each line contains two integers a and b indicating there is a road between city aand city b. (1 ≤ a, b ≤ N)

Output

For each test case, output an integer indicating the number of cities who will choose elder son as their king.

Sample Input

4 
1 2
2 3
3 4

4
1 2
1 3
1 4

Sample Output

2
3

Solution

题意:一个国王要两个儿子分治国家,国土是树状的,大小儿子可以任意选首都,其他城市离哪个首都近,就归哪个王子管。如果一样近,就归大儿子管。大小王子均采取最优策略。问大王子怎么选首都,能获得最多城市。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long ll;
const int INF = INT_MAX;
const int MAXN = 50000 + 10;
using namespace std;
int n, edge_size, ans;
int nex[MAXN], cal[MAXN], ucal[MAXN];
struct node
{
	int u, v, next;
}edge[2 * MAXN];
void dfs(int pre, int u)
{
	int  maxx = -1;
	ucal[u] = ucal[pre] + 1;//这个节点往上数的节点个数
	cal[u] = 1;//这个节点往下数的节点个数
	for (int x = nex[u]; x != -1; x = edge[x].next)
	{
		int v = edge[x].v;
		if (v != pre)
		{
			dfs(u, v);
			cal[u] += cal[v];
			if (cal[v] > maxx)maxx = cal[v];
		}
	}
	if (maxx < n - cal[u])maxx = n - cal[u];
	if (ans < n - maxx)ans = n - maxx;
}
void insert(int u, int v)//双向边
{
	edge[edge_size].u = u;
	edge[edge_size].v = v;
	edge[edge_size].next = nex[u];
	nex[u] = edge_size++;
	edge[edge_size].v = u;
	edge[edge_size].u = v;
	edge[edge_size].next = nex[v];
	nex[v] = edge_size++;
}
void init()
{
	edge_size = 0;
	memset(nex, -1, sizeof(nex));
	ms(cal);
	ans = 0;
}
int main()
{
	while (cin >> n)
	{
		init();
		for (int i = 1; i < n; i++)
		{
			int u, v;
			cin >> u >> v;
			insert(u, v);
		}
		dfs(0, 1);
		cout << ans << endl;
	}
	return 0;
}

欢迎分享与转载,请保留链接与出处。Ocrosoft » ACDream 1015 Double Kings

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址