学步园

代码1：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 1003

#define inf 1<<29

struct node
{
    int v, next, w;
}edge[maxn<<1];
int n, m;


int head[maxn];
int tot;

void init()
{
    tot = 0;
    memset(head, -1, sizeof(head));
}

void add(int x, int y, int w)
{
    edge[tot].v = y;
    edge[tot].w = w;
    edge[tot].next = head[x];
    head[x] = tot++;
}

int minz(int a, int b)
{
    return a < b ? a : b;
}

int dp[1003];

void dfs(int u, int pre, int sum)
{
    int i;
    bool flag = 0;
    int tmp = 0;
    for(i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        int w = edge[i].w;
        if(v == pre) continue;
        dfs(v, u, sum);    
        flag = 1;
        if(w <= sum) tmp += minz(dp[v], w);
        else 
        {
            if(dp[v] < inf)
                tmp += dp[v];
            else flag = 0;
        }
        if(!flag) break;
    }
    if(flag) dp[u] = minz(dp[u], tmp);
}

int main()
{
    int i, j;
    int x, y, w;
    while( ~scanf("%d%d", &n, &m) && (n||m) )
    {
        init();
        for(i = 0; i < n-1; i++)
        {
            scanf("%d%d%d", &x, &y, &w);
            add(x, y, w);
            add(y, x, w);
        }
        int l = 0, r = m;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            for(i = 1; i <= n; i++)
                dp[i] = inf;
            dfs(1, 1, mid);
            if(dp[1] > m) l = mid + 1;
            else r = mid - 1;
            //printf("l = %d r = %d\n", l, r);
        }
        if(l > m) puts("-1");
        else printf("%d\n", l);
    }
    return 0;
}

代码2：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 1003

#define inf 1000001 //注意别太大，不然会超int

struct node
{
    int v, next, w;
}edge[maxn<<1];

int head[maxn];
int tot;
int n, m;

void init()
{
    tot = 0;
    memset(head, -1, sizeof(head));
}

void add(int x, int y, int w)
{
    edge[tot].v = y;
    edge[tot].w = w;
    edge[tot].next = head[x];
    head[x] = tot++;
}

int minz(int a, int b)
{
    return a < b ? a : b;
}

int dp[1003];

void dfs(int u, int pre, int sum)
{
    int i;
    bool flag = 0;
    int tmp = 0;
    for(i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        int w = edge[i].w;
        if(v == pre) continue;
        //printf("v = %d w = %d\n", v, w);
        dfs(v, u, sum);
        if(w <= sum) tmp += minz(dp[v], w);
        else tmp += dp[v];
        flag = 1;
    }
    if(flag) dp[u] = minz(dp[u], tmp);
}

int main()
{
    int i, j;
    int x, y, w;
    while( ~scanf("%d%d", &n, &m) && (n||m) )
    {
        init();
        for(i = 0; i < n-1; i++)
        {
            scanf("%d%d%d", &x, &y, &w);
            add(x, y, w);
            add(y, x, w);
        }
        int l = 0, r = m;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            for(i = 1; i <= n; i++)
                dp[i] = inf;
            dfs(1, 1, mid);
            if(dp[1] > m) l = mid + 1;
            else r = mid - 1;
            //printf("l = %d r = %d\n", l, r);
        }
        if(l > m) puts("-1");
        else printf("%d\n", l);
    }
    return 0;
}