AOJ 911.组队分配

135


题目



点击显/隐题目

有一个n个节点n-1条边组成的树。
每个点看成一个人,连接u和v的边看成是“中意关系”,即u和v两个人都想和对方组队。每个人希望组队的对象有可能有多个。
一支队伍由且仅由两个人组成,并且如果u和v组队了,那么u、v将不能和其他人再组成一支队。
现在问你,这n个人最多能组成多少支队伍。(允许某些人组不了队)
一种可行的组队方案:
1与3组队
4与5组队
最多组成2支队


第一行输入一个整数n,m(1<=n<=200000)
接下来n-1行,每行两个整数u,v,表示u和v两个人都想和对方组队。
数据保证是一个合法的树。


输出一个整数,表示最多能组成多少支队伍。


5
1 2
1 3
2 4
4 5


2




题解



下意识写了匈牙利算法,不过这道题会爆时间
再仔细看一下题目
可以发现其实求树上父节点和子节点配对能配多少对
可以用动态规划求解

dp[t][0]表示编号为t的节点往下并且不选取节点t能达到的最多对数
dp[t][1]表示编号为t的节点往下并且选取节点t能达到的最多对数

很容易就可以发现 dp[t][0] = sum{ max(dp[child][0], dp[child][1])) }
dp[t][1] 则根据是否存在没有选取的子节点(上一步有使用dp[child][0])有dp[t][1] = dp[t][0]dp[t][1] = dp[t][0] + 1



代码


点击显/隐代码
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int maxn = 200005;

vector<int> e[maxn];
int n;
int parent[maxn];
int dp[maxn][2];

void init() {
memset(parent, 0, (n + 5) * sizeof(int));
for (int i = 0; i <= n; ++i)
e[i].clear();
}

void addEdge(int u, int v) {
e[u].push_back(v);
e[v].push_back(u);
}

void dfs(int t) {
// printf("dfs(%d)\n", t);
dp[t][0] = dp[t][1] = 0;
bool emptyChild = false;
for (auto child : e[t]) {
if (parent[t] != child) {
parent[child] = t;
dfs(child);
if (dp[child][0] < dp[child][1]) {
dp[t][0] += dp[child][1];
} else {
emptyChild = true;
dp[t][0] += dp[child][0];
}
}
}
dp[t][1] = dp[t][0] + emptyChild;
// printf("dp[%d]={%d,%d}\n", t, dp[t][0], dp[t][1]);
}

int main() {
while (~scanf("%d", &n)) {
init();
for (int i = 1; i < n; ++i) {
int a, b;
scanf("%d%d", &a, &b);
addEdge(a, b);
}
dfs(1);
printf("%d\n", max(dp[1][0], dp[1][1]));
}
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论