Hidden Supervisors
- Input file: hidden.in
- Output file: hidden.out
- Time limit: 3 seconds
- Memory limit: 512 megabytes
Helena works in a big company as a psychologist. Her task is to organize a team building game to
enhance social relations between employees. Each employee except the Big boss has a single supervisor.
So, employees of the company form a tree where each employee is a node, and the parent of that node is
their supervisor. The root of the tree is the Big boss.
A team building game requires teams of two people. Every team should consist of an employee and their
supervisor.
Helena asked every employee except the Big boss to send their supervisor ID. Some of them didn’t reply.
She is going to assign a fake supervisor to every employee that didn’t reply, so that she could arrange as
many teams as possible. And, of course, fake and real supervisors must form a tree.
Helena had a difficult, but a successful day organizing the event. Will you be able to assign fake
supervisors?
Input
The first line of the input contains a single integer n — the number of employees in the company
(2 ≤ n ≤ 100 000).
The following line contains n − 1 integers p2, p3, . . . , pn, where pi is the supervisor of employee i (0 ≤ pi ≤ n). If employee i didn’t reply to Helena, pi equals zero, and she needs to assign a fake supervisor to that employee. The Big boss has the number 1.
It’s possible to assign a fake supervisor to each employee that didn’t reply to Helena so that all employees
will form a tree having the Big boss as a root.
Output
In the first line output a single integer m — the maximum possible number of arranged teams.
The next line should contain supervisors: n−1 integers, i-th of which denoting the supervisor of employee
i + 1 (either fake or real). Of course, all real supervisors should be preserved, and employees must form
a tree. It should be possible to arrange m teams using specified supervisors.
链接
https://cn.vjudge.net/problem/Gym-101612H
题意
有一棵节点数为n的树，根节点为1，有些节点的父节点没有确定，可以将它们的父节点连在别的节点数，但是要保证是一棵树，现要求节点数为2（包含一个子节点和一个父节点）的最大匹配数量。
题解
计算每个连通块的最大匹配情况，找到没有匹配的点。将连通块按照未匹配节点的数量从大到小排序，对于一个连通块，如果根节点没有匹配，那么将它与已有空闲节点相连，匹配数加1；如果根节点已匹配，那么将根节点的父节点直接设为1。
实现时，维护一个空闲队列，首先将包含节点1的块空闲节点加入，然后从空闲节点多的树开始贪心的与队列连边。
摘自题解：传送门。
“树上的最大匹配可以自底向上贪心求出，且选根的匹配数至多比不选根的多1”。
代码
| Status | Accepted |
|---|---|
| Time | 108ms |
| Memory | 10736kB |
| Length | 2256 |
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100010;
int n, fa[maxn], degree[maxn], match[maxn], ans, tot;
struct Node // 以当前节点为根节点的未匹配的子节点
{
int rt, size;
vector <int> unmatch;
bool operator < (const Node & r) const
{
return size > r.size;
}
}node[maxn];
vector <int> E[maxn], unmatch, V;
void dfs(int u)
{
match[u] = 0;
for (int i = 0; i < E[u].size(); ++i)
{
int v = E[u][i];
dfs(v);
if (!match[u] && !match[v])
{
match[u] = v;
match[v] = u;
++ans;
}
if (!match[v]) // 未匹配
unmatch.push_back(v);
}
}
int main()
{
freopen("hidden.in", "r", stdin);
freopen("hidden.out", "w", stdout);
scanf("%d", &n);
for (int i = 2; i <= n; ++i)
{
scanf("%d", fa + i);
if (fa[i])
{
++degree[i];
E[fa[i]].push_back(i);
}
}
ans = tot = 0;
V.clear();
for (int i = 1; i <= n; ++i)
{
if (degree[i] == 0)
{
unmatch.clear();
dfs(i);
if (i == 1 || match[i]) // 当前节点为1或者根节点已匹配
{
fa[i] = 1;
for (int j = 0; j < unmatch.size(); ++j)
V.push_back(unmatch[j]);
if (i == 1 && !match[i]) // 1未匹配
V.push_back(i);
}
else // 根节点未匹配，保存信息
{
node[tot].rt = i;
node[tot].size = unmatch.size();
node[tot++].unmatch = unmatch;
}
}
}
sort(node, node + tot); // 从大到小贪心
for (int i = 0; i < tot; ++i)
{
int x = node[i].rt;
if (V.size())
{
++ans;
int u = V.back();
fa[x] = u;
V.pop_back();
}
else
{
fa[x] = 1;
V.push_back(x);
}
for (int j = 0; j < node[i].size; ++j)
V.push_back(node[i].unmatch[j]);
}
printf("%d\n", ans);
printf("%d", fa[2]);
for (int i = 3; i <= n; ++i)
printf(" %d", fa[i]);
printf("\n");
return 0;
}The end.
2018-08-17 星期五