学步园

http://poj.org/problem?id=3107 

给定一棵树，取去掉某一节点后形成子树的最大节点数，求使这个数最小的节点。

去掉某一节点后，形成的树包括子树和原树去掉以这个点为根的树所形成的树，在这几个树中求最大值即可。

节点数的计算可用回溯，过程中选取最大值。

貌似是我第一个用邻接表存边的题，贴下模板。

邻接表存边code:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000;
class edge{
    public:
    int v,nex;
};edge e[nMax];
int n,k,head[nMax];      //head[i]是以点i为起点的链表头部
void addedge(int a,int b){//向图中加有向边的算法，注意加上的是有向边
    //b为a的后续节点既是a---->b
    e[k].v=b;
    e[k].nex=head[a];
    head[a]=k;
    k++;
}
int main(){
    int i,a,b,w,k=1;
    scanf("%d",&n);
    memset(head,0,sizeof(head));
    for(i=0;i<n;i++){
        scanf("%d%d",&a,&b);
        addedge(a,b);                                 //添加一条由a指向b的边
    }
    cin>>w;                                           //输出w点所指向的点
    for(i=head[w];i;i=e[i].nex){
        cout<<e[i].v<<endl;
    }
    cout<<"end\n";
    return 0;} 

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define Max(a, b) a>b?a:b
using namespace std ;
const int MAX = 50001 ;
int vis[MAX], head[MAX], ans[MAX], num[MAX] ;
int n, k, Min, sum ;
struct Edge{
    int v, next ;
}edge[2*MAX] ;
void addedge(int a, int b){
    edge[k].v = b ;
    edge[k].next = head[a] ;
    head[a] = k ++ ;
}
void dfs(int x){
    int i, v, min = -1 ;
    num[x] = 1 ;
    vis[x] = 1 ;
    for(i=head[x]; i; i=edge[i].next){
        v = edge[i].v ;
        if(vis[v])  continue ;
        dfs(v) ;
        num[x] += num[v] ;//计算节点数
        min = Max(min, num[v]) ;//选取子树中节点最多的
    }
    min = Max(min, n-num[x]) ;//子树中较大者与除去root为x的树相比较
    if(min<Min){
        Min = min ;
        sum = 1 ;
        ans[0] = x ;
    }else if(min==Min){
        ans[sum++] = x ;
    }
}
int main(){
    int x, y ;
    scanf("%d", &n) ;
    k = 1 ;
    memset(head, 0, sizeof(head)) ;
    for(int i=1; i<n; i++){
        scanf("%d%d", &x, &y) ;
        addedge(x, y) ;
        addedge(y, x) ;
    }
    memset(num, 0, sizeof(num)) ;
    memset(vis, 0, sizeof(vis)) ;
    Min = MAX ;
    dfs(1) ;
    sort(ans, ans+sum) ;
    for(int i=0; i<sum; i++)
        printf("%d ", ans[i]) ;
    printf("\n") ;
    return 0 ;}