[关闭]
@ysner 2018-06-10T11:55:41.000000Z 字数 2342 阅读 1837

[SCOI2005]王室联邦

贪心


题面

某个国王想把他的国家划分成若干个省。。。
他的国家有个城市,编号为。一些城市之间有道路相连,任意两个不同的城市之间有且仅有一条直接或间接的道路。为了防止管理太过分散,每个省至少要有个城市,为了能有效的管理,每个省最多只有个城市。
每个省必须有一个省会,这个省会可以位于省内,也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市(除了最后一个城市,即该省省会)都必须属于该省。
一个城市可以作为多个省的省会。

解析

看完题,显然能想到一个贪心,就是进行树的,一旦发现以某个点为根的子树大小大于等于,则把这颗子树划为一个省。最后根节点那里一般有个点未被划入省中,因,划入最后一个省(离根节点最近)即可。
具体把子树划为省的方法是标记子树根节点,稍后再一遍下放标记。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int N=1200;
  14. int n,b,bl[N],cap[N],h[N],cnt,sz[N],top,pro[N];
  15. struct Edge{int to,nxt;}e[N<<1];
  16. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  17. il void dfs(re int u,re int fa)
  18. {
  19. sz[u]=1;
  20. for(re int i=h[u];i+1;i=e[i].nxt)
  21. {
  22. re int v=e[i].to;
  23. if(v==fa) continue;
  24. dfs(v,u);
  25. sz[u]+=sz[v];
  26. }
  27. if(sz[u]>b) bl[u]=++top,cap[top]=u,sz[u]=0;
  28. }
  29. il void lab(re int u,re int fa,re int id)
  30. {
  31. if(!bl[u]) bl[u]=id,pro[id]++;else id=bl[u],pro[bl[u]]++;
  32. if(!cap[id]) cap[id]=u;
  33. for(re int i=h[u];i+1;i=e[i].nxt)
  34. {
  35. re int v=e[i].to;
  36. if(v==fa) continue;
  37. lab(v,u,id);
  38. }
  39. }
  40. int main()
  41. {
  42. memset(h,-1,sizeof(h));
  43. n=gi();b=gi();
  44. fp(i,1,n-1)
  45. {
  46. re int u=gi(),v=gi();
  47. add(u,v);add(v,u);
  48. }
  49. dfs(1,0);
  50. lab(1,0,top);
  51. printf("%d\n",top);
  52. fp(i,1,n) printf("%d ",bl[i]);puts("");
  53. fp(i,1,top) printf("%d ",cap[i]);puts("");
  54. return 0;
  55. }

但这样只能获得
因为这么弄就排除了一个城市为多省省会省会在该省省外的情况。
这种情况表明一个省份是可以不联通的,即一个节点有两个子节点,两个子节点属于一个省,根节点属于另一个省。
造数据就是一个根节点,它的所有子节点子树大小都不到,但它自己子树大小超过
维护这类省份就只能用栈了。注意搜到一节点时最后再把该节点加入栈。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int N=1200;
  14. int n,b,bl[N],cap[N],h[N],cnt,sta[N],tot,top;
  15. struct Edge{int to,nxt;}e[N<<1];
  16. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  17. il void dfs(re int u,re int fa)
  18. {
  19. re int now=tot;
  20. for(re int i=h[u];i+1;i=e[i].nxt)
  21. {
  22. re int v=e[i].to;
  23. if(v==fa) continue;
  24. dfs(v,u);
  25. if(tot-now>=b) {cap[++top]=u;while(tot^now) bl[sta[tot--]]=top;}
  26. }
  27. sta[++tot]=u;
  28. }
  29. int main()
  30. {
  31. memset(h,-1,sizeof(h));
  32. n=gi();b=gi();
  33. fp(i,1,n-1)
  34. {
  35. re int u=gi(),v=gi();
  36. add(u,v);add(v,u);
  37. }
  38. dfs(1,0);
  39. while(tot) bl[sta[tot--]]=top;
  40. printf("%d\n",top);
  41. fp(i,1,n) printf("%d ",bl[i]);puts("");
  42. fp(i,1,top) printf("%d ",cap[i]);puts("");
  43. return 0;
  44. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注