AOJ 911.组队分配

344


题目



点击显/隐题目

有一个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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论