hdu 3586 最小代价切断根与叶子联系

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3586

http://blog.csdn.net/woshi250hua/article/details/7639423

题目大意：给定n个敌方据点，1为司令部，其他点各有一条边相连构成一棵树，每条边都有一个权值cost表示破坏这条边的费用，叶子节点为前线。现要切断前线和司令部的联系，每次切断边的费用不能超过上限limit，问切断所有前线与司令部联系所花费的总费用少于m时的最小limit。1<=n<=1000,1<=m<=100万

先考虑x的代价能否满足条件。对于某个节点rt有两种情况。

if(tree[i].val < x) dp[rt] += min(tree[i].val,dp[son])

else dp[rt]+=dp[son];

因为这里只用给叶子节点赋值，因为是双向边，不能用head[rt]==-1判断。这里可以用flag来判断。

x的情况分析好后，就可以用二分来找到答案了

#include <iostream>

#include <string>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <cctype>

#include <vector>

#include <iterator>

#include <set>

#include <map>

#include <sstream>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))

#define pf printf

#define sf scanf

#define spf sprintf

#define pb push_back

#define debug printf("!\n")

#define MAXN 1000+5

#define MAX(a,b) a>b?a:b

#define blank pf("\n")

#define LL long long

#define ALL(x) x.begin(),x.end()

#define INS(x) inserter(x,x.begin())

#define pqueue priority_queue

#define INF 0x3f3f3f3f

int n,m;

struct node{int y,val,next;}tree[MAXN<<];

int head[MAXN],vis[MAXN],ptr=,dp[MAXN];

void init()

{

    mem(head,-);

    mem(vis,);

    mem(dp,);

    ptr=;

}

void add(int x,int y,int val)

{

    tree[ptr].y = y;

    tree[ptr].val = val;

    tree[ptr].next = head[x];

    head[x] = ptr++;

}

int cost;

void dfs(int rt,int limit)

{

    vis[rt]=;

    int flag = ;

    for(int i = head[rt];i!=-;i=tree[i].next)

    {

        int y = tree[i].y;

        if(vis[y]) continue;

        flag = ;

        dfs(y);

        if(tree[i].val < limit)

        {

            dp[rt] += min(tree[i].val,dp[y]);

        }

        else

        {

            dp[rt] += dp[y];

        }

    }

    if(!flag) dp[rt]=INF;

}

int main()

{

    int i,j,k,t;

    while(~sf("%d%d",&n,&m))

    {

        init();

        int mx = ;

        for(i=;i<n;i++)

        {

            int x,y,z;

            sf("%d%d%d",&x,&y,&z);

            add(x,y,z);

            add(y,x,z);

            if(z>mx) mx = z;

        }

        dfs();

        int lo = ,hi = mx,mid;

        while(lo<=hi)

        {

            mem(dp,);

            mem(vis,);

            mid = (lo+hi)>>;

            dfs(,mid);

            if(dp[]<=m) hi = mid-;

            else lo = mid+;

        }

        pf("%d\n",lo);

    }

}

巴特西

hdu 3586 最小代价切断根与叶子联系

最新文章

热门文章