[POI2012]Salaries

时间:2024-10-31 09:32:56

题目大意:
  给定一棵n带权树,每个点的权值在[1,n]范围内且互不相等,并满足子结点的权值一定小于父结点。
  现在已知一个包含根结点的联通块中个点的权值,求剩下哪些点的权值能够被求出,并求出这些权值。

思路:
  贪心。
  很显然,对于某一个结点x,如果当前只有一个可取的权值w,且小于其父结点的权值,那么这个结点的权值一定是w。
  事实上所有未知结点权值都可以尝试用这样的方法得出,关键是如何唯一确定下这个权值w。
  我们可以用一个数组max记录每个结点权值的上界,再用一个数组last记录小于某个权值能取的最大权值。
  max数组可以用一趟DFS递归出来。
  然后顺序枚举每一个权值,如果可用就加入到一个“黑箱”中,如果现在黑箱中只有一个权值w并且有未知权值的结点,说明这个节点的权值就是w。
  然后如果现在黑箱中有多个权值,未知的结点也很多,那么这些权值就作废。

 #include<cstdio>
#include<cctype>
#include<vector>
inline int getint() {
char ch;
while(!isdigit(ch=getchar()));
int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int V=;
std::vector<int> c[V];
int n;
int w[V],s[V],par[V],max[V],cnt[V],last[V],root;
int find(const int x) {
return x==last[x]?x:last[x]=find(last[x]);
}
void dfs(const int x) {
if(!max[x]) {
max[x]=find(max[par[x]]-);
s[max[x]]=x;
cnt[max[x]]++;
}
for(unsigned i=;i<c[x].size();i++) {
dfs(c[x][i]);
}
}
int main() {
n=getint();
for(int i=;i<=n;i++) last[i]=i;
for(int i=;i<=n;i++) {
int p=getint();
w[i]=max[i]=getint();
if(p!=i) {
c[p].push_back(i);
par[i]=p;
} else {
root=i;
w[i]=n;
}
last[w[i]]=w[i]-;
}
dfs(root);
for(int i=,tmp=;i<=n;i++) {
if(last[i]==i) tmp++;
if(cnt[i]&&tmp==) w[s[i]]=i;
tmp-=cnt[i];
}
for(int i=;i<=n;i++) printf("%d\n",w[i]);
return ;
}