BZOJ1131: [POI2008]Sta
题意：给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大。
题解：记录每个点的深度，再根据根节点的深度和逐层推导出其他点的深度和。
我用的是BFS
#include <stdio.h>View Code
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
int n,cnt,ans;
int head[1000010],next[2000010],to[2000010],fa[1000010],s[1000010];
ll f[1000010],g[1000010],siz[1000010];
queue<int> q;
void add(int a,int b)
{
to[cnt]=b;
next[cnt]=head[a];
head[a]=cnt++;
}
int main()
{
scanf("%d",&n);
memset(head,-1,sizeof(head));
int i,a,b,u;
for(i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
q.push(1);
while(!q.empty())
{
u=q.front();
q.pop();
s[++s[0]]=u;
siz[u]++;
for(i=head[u];i!=-1;i=next[i])
{
if(to[i]!=fa[u])
{
fa[to[i]]=u;
q.push(to[i]);
}
}
}
for(i=n;i>=2;i--)
{
siz[fa[s[i]]]+=siz[s[i]];
f[fa[s[i]]]+=siz[s[i]]+f[s[i]]; //f[i]表示i的所有儿子到i的深度之和
}
g[1]=f[ans=1];
for(i=2;i<=n;i++)
{
g[s[i]]=g[fa[s[i]]]+n-(siz[s[i]]<<1); //g[i]表示所有点到i的距离之和，可由g[fa[i]]推出
if(g[ans]<g[s[i]]||(g[ans]==g[s[i]]&&ans>s[i]))
ans=s[i];
}
printf("%d",ans);
return 0;
}
POJ3107:Godfather
题意：在树中找一个点，使去掉这个点后，剩余的所有子树节点个数的最大值最小，求满足要求的所有节点。
题解：求出每个子树的节点个数size[x]，则答案为min(size[y],n-size[x]),y是x的儿子。
#include <stdio.h>View Code
#include <string.h>
#include <iostream>
using namespace std;
const int maxn=50010;
int n,cnt,minn;
int head[maxn],to[maxn<<1],next[maxn<<1],s[maxn],f[maxn],sta[maxn];
int readin()
{
int ret=0; char gc;
while(gc<'0'||gc>'9') gc=getchar();
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret;
}
void add(int a,int b)
{
to[cnt]=b;
next[cnt]=head[a];
head[a]=cnt++;
}
void dfs(int x,int fa)
{
s[x]=1;
for(int i=head[x];i!=-1;i=next[i])
{
if(to[i]!=fa)
{
dfs(to[i],x);
s[x]+=s[to[i]];
f[x]=max(f[x],s[to[i]]);
}
}
f[x]=max(f[x],n-s[x]);
minn=min(minn,f[x]);
}
int main()
{
n=readin();
memset(head,-1,sizeof(head));
int i,a,b;
for(i=1;i<n;i++)
{
a=readin(),b=readin();
add(a,b),add(b,a);
}
minn=1<<30;
dfs(1,0);
for(i=1;i<=n;i++) if(f[i]==minn) sta[++sta[0]]=i;
for(i=1;i<sta[0];i++) printf("%d ",sta[i]);
printf("%d",sta[sta[0]]);
return 0;
}
POJ1655:Balancing Act
题意：同POJ3107
#include <stdio.h>View Code
#include <iostream>
#include <string.h>
using namespace std;
const int maxn=20010;
int n,minn,ans,cnt;
int s[maxn],to[maxn<<1],next[maxn<<1],head[maxn];
int readin()
{
int ret=0; char gc;
while(gc<'0'||gc>'9') gc=getchar();
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret;
}
void add(int a,int b)
{
to[cnt]=b;
next[cnt]=head[a];
head[a]=cnt++;
}
void dfs(int x,int fa)
{
int t=0;
s[x]=1;
for(int i=head[x];i!=-1;i=next[i])
{
if(to[i]!=fa)
{
dfs(to[i],x);
s[x]+=s[to[i]];
t=max(t,s[to[i]]);
}
}
t=max(t,n-s[x]);
if(t<minn||(t==minn&&x<ans)) ans=x,minn=t;
}
void work()
{
n=readin();
memset(head,-1,sizeof(head));
ans=cnt=0,minn=1<<30;
int i,a,b;
for(i=1;i<n;i++)
{
a=readin(),b=readin();
add(a,b),add(b,a);
}
dfs(1,0);
printf("%d %d\n",ans,minn);
}
int main()
{
int t=readin();
while(t--) work();
return 0;
}
BZOJ1827:[Usaco2010 Mar]gather 奶牛大集会
题意：与上一题差不多，只不过不同的点有不同的牛居住，求的是所有牛到核心的最小总路程