hdu-6228 Tree 2017年ICPC沈阳站L题 DFS+思维
程序员文章站
2022-05-19 20:55:24
...
题目链接
题意
题目比较难理解,读懂样例就会好一点。大概就是给出一棵有N个结点的树,有K种色彩对树的结点进行染色,然后连接所有相同颜色的点,并将经过的边组成一个边集Ei,最后取所有边集的交集的最大值。说白了就是连接所有颜色相同的点,看有几个边所有颜色的路线都经过。求这个的最大值。
题解
这个题最开始想的是,每个点可以是多个边的结点,因为我们需要考虑某个边是否能让所有的集合都经过,换而言之,只有这个点有多个边经过,那么这个点对应的边就是交集边。所以计算每个结点经过边的数量,大于1的全部整合起来再减1就是答案。当然这只是最简单的思想,绝对是错的。不过整体思路是没问题的:即找到那些边可以被经过多次。
为了使一个边能被所有的颜色经过,最简单思路:这个结点的所有子结点的数量>=K,这样如果子结点最大可能是所有种类的颜色都从这个结点经过,那么这个边就是解集边。
第一次这样写的时候WA了,后来才想到这样我们可能将根或者比较高层的结点也算进去,因为是无向图,所以我们应该考虑以一个结点为中心,分隔整个图,要求左边的结点和右边的结点同时>=K,那么这个结点最大可能下能经过至少K次,就是解集边。
那么就比较容易解决了,首先DFS统计所有结点的子结点数量。因为一定是树,那么随便找个结点当做根就可以,统计的子结点数M就是一侧的结点数量,另一侧就是N-M。最后遍历整个结点,满足 && 的结点就是解集边的一个点。
数据的储存方面,我是利用vector数组,即利用邻接表的方式储存,满足题目给出的要求。
C++ AC 代码 140ms
#include<iostream>
#include<vector>
#include<list>
#include<string>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<queue>
#include<sstream>
#include<iterator>
#include<math.h>
#include<malloc.h>
#include<string.h>
#include<stack>
#include<functional>
#define TIME std::ios::sync_with_stdio(false)
#define LL long long
#define MOD 1000000007
#define MAX 201000
#define INF 0x3f3f3f3f
using namespace std;
int T,N,K;
int number[MAX],step[MAX];
vector<int> maps[MAX];
int dfs(int root){
int len = maps[root].size();
if(len == 0) return 1;
for(int i = 0;i < len;i++){
if(step[i] == 1) continue;
step[i] = 1;
number[root] += dfs(maps[root][i]);
}
return number[root];
}
int main() {
TIME;
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&K);
memset(step,0,sizeof(step));
for(int i = 0;i <= N;i++){
maps[i].clear();
number[i] = 1;
}
int a,b;
for(int i = 0;i < N-1;i++){
scanf("%d%d",&a,&b);
maps[a].push_back(b);
maps[b].push_back(a);
}
step[1] = 1;
dfs(1);
int ans = 0;
for(int i = 1;i <= N;i++){
if(number[i] >= K && number[i] <= (N - K)){
ans++;
}
}
printf("%d\n",ans);
}
system("pause");
return 0;
}