跳至正文

NOIp 2007 提高组 4 树网的核

  这个题目网上有很多题解,不过直接照抄的话确实不太好,我还是说说我自己的过程吧。
  首先,可以知道的是“核”越长越好,确实说不太清楚,看下面的图吧:

NOIp 2007 提高组 4 树网的核 - NeWorldMaker - My S-K-Y
   如果核是A-B的话,A-B距离X的值为B到X的距离,假设为x,即B至X的距离,但是如果核是A-C的话,那么A-C距离X的值就会小于x,所以“核”还是越长越好!
  后只需要从一条直径上寻找核就可以了,为什么的话,我觉得吧,最好的“核”选择有两点,第一点如上所述,越长越好;我觉得第二点就是越靠近中点越好,至于为什么的话,你自己想想,中点距离所有点的最长距离就是半径,而重点之外的就会大于半径,那么不就是长了?所以的话还是越靠近中点越好,所以从一条直径搜索应该是够了的(我知道这样解释是行不通的,但是我自己也不知道是什么原因,只好这么说了。)
  直径的寻找就是随意使用一个点寻找最远的距离的节点,这就是一条直径的一端,然后从最远距离的节点出发再寻找一次最远距离,这就构成了一条直径,至于为什么,距离一个节点最远的距离为什么一定是一条直径的一端,我的理解是距离一个节点最远的距离一定是距离中点的距离加上半径的长度,也就是说最远的距离是先经过中点再去寻找半径。
  寻找到了半径再根据s求枚举所有的核的可能,这里要注意的一点就是(我烦的错误),寻找d(F, V)的时候是先取距离整条边最长的节点,然后取所有边(核)中最小的一个。
  代码附上:
#include <stdio.h>
#include <string.h>
#define bzero(a, b) memset((a), 0, (b))
int n, s;
int map[300][300];

int ans = 10000000;

int used[300];
int prev[300];
int dist[300];
int max, loc;

void d(int i, int sum)
{
        int j;
        used[i] = 1;
        if(sum > max){
                loc = i;
                max = sum;
        }
        for(j = 0; j < n; j++){
                if(!used[j] && map[i][j]){
                        dist[j] = sum + map[i][j];
                        prev[j] = i;
                        d(j, dist[j]);
                }
        }
}

void dfs(int node)
{
        bzero(used, sizeof(used));
        bzero(prev, sizeof(prev));
        bzero(dist, sizeof(dist));
        max = 0;
        prev[node] = –1;
        d(node, 0);
}

int lis[300];
int lenth;

void find(void)
{
        int i;
        dfs(0);
        dfs(loc);
        i = loc;
        while(i != –1){
                lis[lenth++] = i;
                i = prev[i];
        }
}

int tmp[90000];

//先删除本路径, 再逐个dfs,, 再恢复路径 
void deal(int a, int b)
{
        int i, m;
        //删除本路劲 
        for(i = a; i < b; i++){
                tmp[i – a] = map[lis[i]][lis[i + 1]];
                map[lis[i]][lis[i + 1]] = 0;
                map[lis[i + 1]][lis[i]] = 0;
        }
        //获取距离本路径最远的距离
        m = 0;
        for(i = a; i <= b; i++){
                dfs(lis[i]);
                if(m < max){
                        m = max;
                }
        }
        //更新ans 
        if(ans > m){
                ans = m;
        }
        //恢复路径 
        for(i = a; i < b; i++){
                map[lis[i]][lis[i + 1]] = tmp[i – a];
                map[lis[i + 1]][lis[i]] = tmp[i – a];
        }
}

void work(void)
{
        int i, j;
        int d;
        for(i = 0; i < lenth; i++){
                //寻找尽可能长的核 
                d = map[lis[i]][lis[i + 1]];
                for(j = i + 1; j < lenth && d <= s; j++){ 
                        d += map[lis[j]][lis[j + 1]];
                }
                //获取此核的长度, 并更新ans 
                deal(i, j – 1);
        }
}

int main(void)
{
        int i;
        int a, b, c;
        scanf("%d%d", &n, &s);
        for(i = 1; i < n; i++){
                scanf("%d%d%d", &a, &b, &c);
                a–, b–;
                map[a][b] = map[b][a] = c;
        }
        //寻找半径,, 然后用lis数组记录半径的线路 
        find();
        //寻找最小的偏心距,,  用ans记录 
        work();
        printf("%d\n", ans);
        return 0;
}

发表评论

您的电子邮箱地址不会被公开。