@ysner
2018-06-10T11:55:41.000000Z
字数 2342
阅读 1863
栈
贪心
某个国王想把他的国家划分成若干个省。。。
他的国家有个城市,编号为。一些城市之间有道路相连,任意两个不同的城市之间有且仅有一条直接或间接的道路。为了防止管理太过分散,每个省至少要有个城市,为了能有效的管理,每个省最多只有个城市。
每个省必须有一个省会,这个省会可以位于省内,也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市(除了最后一个城市,即该省省会)都必须属于该省。
一个城市可以作为多个省的省会。
看完题,显然能想到一个贪心,就是进行树的,一旦发现以某个点为根的子树大小大于等于,则把这颗子树划为一个省。最后根节点那里一般有个点未被划入省中,因,划入最后一个省(离根节点最近)即可。
具体把子树划为省的方法是标记子树根节点,稍后再一遍下放标记。
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1200;
int n,b,bl[N],cap[N],h[N],cnt,sz[N],top,pro[N];
struct Edge{int to,nxt;}e[N<<1];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
il void dfs(re int u,re int fa)
{
sz[u]=1;
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
sz[u]+=sz[v];
}
if(sz[u]>b) bl[u]=++top,cap[top]=u,sz[u]=0;
}
il void lab(re int u,re int fa,re int id)
{
if(!bl[u]) bl[u]=id,pro[id]++;else id=bl[u],pro[bl[u]]++;
if(!cap[id]) cap[id]=u;
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;
if(v==fa) continue;
lab(v,u,id);
}
}
int main()
{
memset(h,-1,sizeof(h));
n=gi();b=gi();
fp(i,1,n-1)
{
re int u=gi(),v=gi();
add(u,v);add(v,u);
}
dfs(1,0);
lab(1,0,top);
printf("%d\n",top);
fp(i,1,n) printf("%d ",bl[i]);puts("");
fp(i,1,top) printf("%d ",cap[i]);puts("");
return 0;
}
但这样只能获得。
因为这么弄就排除了一个城市为多省省会和省会在该省省外的情况。
这种情况表明一个省份是可以不联通的,即一个节点有两个子节点,两个子节点属于一个省,根节点属于另一个省。
造数据就是一个根节点,它的所有子节点子树大小都不到,但它自己子树大小超过。
维护这类省份就只能用栈了。注意搜到一节点时最后再把该节点加入栈。
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1200;
int n,b,bl[N],cap[N],h[N],cnt,sta[N],tot,top;
struct Edge{int to,nxt;}e[N<<1];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
il void dfs(re int u,re int fa)
{
re int now=tot;
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
if(tot-now>=b) {cap[++top]=u;while(tot^now) bl[sta[tot--]]=top;}
}
sta[++tot]=u;
}
int main()
{
memset(h,-1,sizeof(h));
n=gi();b=gi();
fp(i,1,n-1)
{
re int u=gi(),v=gi();
add(u,v);add(v,u);
}
dfs(1,0);
while(tot) bl[sta[tot--]]=top;
printf("%d\n",top);
fp(i,1,n) printf("%d ",bl[i]);puts("");
fp(i,1,top) printf("%d ",cap[i]);puts("");
return 0;
}