[POI2012]Salaries

题目大意：
　　给定一棵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 ;

 }

巴特西

[POI2012]Salaries

最新文章

热门文章