HDU 3586-Information Disturbing（树形dp）

时间：2022-11-01 16:03:26

题意：

n个节点的通信连接树，切断每个边有一定的花费，要你切断边，在总花费不超过m的前提，使所有的其他节点都不能和节点1（根）连通，切边时有花费上限，让你最小化这个上限。

分析：最小化最大值，想到二分，二分上限求符合条件的总花费和m比较。

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF=<<;

const int mod =  ;

struct edge{

    int t,w;

};

vector<edge>e[];

int dp[],n,m,used[];

void dfs(int root,int limit){

    used[root]=;

    int f=,tmp=;

    for(int i=;i<e[root].size();++i){

        edge d=e[root][i];

        int son=d.t;

        int c=d.w;

        if(used[son])continue;

        f=;

        dfs(son,limit);

        if(c<=limit){

            tmp+=min(dp[son],c);//小于上限，可切可不切

        }

        else tmp+=dp[son];//大于上限不能切断

    }

    if(f)

    dp[root]=tmp;

    else

    dp[root]=INF;

}

int main()

{

    while(~scanf("%d%d",&n,&m)){

        if(n==&&m==)break;

        int a;

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

            e[i].clear();

        for(int i=;i<n-;++i){

            edge b;

            scanf("%d%d%d",&a,&b.t,&b.w);

            e[a].push_back(b);

            int tt=b.t;

            b.t=a;

            e[tt].push_back(b);

        }

        int l=,r=m,ff=-;

        while(l<=r){

            memset(dp,,sizeof(dp));

            memset(used,,sizeof(used));

            int mid=(l+r)>>;

            dfs(,mid);

            if(dp[]<=m){r=mid-;ff=mid;}

            else l=mid+;

        }

        printf("%d\n",ff);

    }

return ;

}

相关文章