首页 > 代码库 > HDU 3586 Information Disturbing

HDU 3586 Information Disturbing

2024-07-14 19:16:21   216人阅读

题意：n各节点其中1号是司令节点，叶子节点是收集信息的节点.现在破坏一些编使这个信息结构瘫痪（就是 让叶子节点和1号节点不连通）；

　　要求他切割的边的最大值最小，且和不能超过M

解法：很普通的的二分答案，用树形DP判断这个解是否可行。

　　子啊 回溯合并的时候

　　如果这个边的cost>枚举的答案 肯定dp 值加等 儿子节点 的dp值

　　否则i加等            MIN（ 儿子节点的dp值，cost）；

#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>#include <cstdlib>using namespace std;int n,m;const int maxn=1003;const int INF=1e6+7;struct Edge{    int to,dis,pre;    Edge(int to=0,int dis=0,int pre=0):to(to),dis(dis),pre(pre){}};Edge edge[maxn*2];int head[maxn],pos;int dp[maxn];void add_edge(int s,int to,int dis){    edge[pos]=Edge(to,dis,head[s]);    head[s]=pos++;}void inint(){    memset(head,-1,sizeof(head));    pos=0;}bool jude(){    return dp[1]<=m;}void dfs(int pa,int s,int mid){    dp[s]=0;    for(int w=head[s];~w;w=edge[w].pre)    {        Edge &tmp=edge[w];        if(tmp.to==pa)continue;        dfs(s,tmp.to,mid);        if(tmp.dis<=mid)dp[s]+=min(dp[tmp.to],tmp.dis);        else            dp[s]+=dp[tmp.to];    }    if(dp[s]==0)dp[s]=INF;}int main(){    int a,b,c;    while(~scanf("%d%d",&n,&m))    {        if(n==0&&m==0)break;        inint();        for(int i=2;i<=n;i++)        {            scanf("%d%d%d",&a,&b,&c);            add_edge(b,a,c);            add_edge(a,b,c);        }        int l,r;        l=0,r=1000000;        while(l<r)        {            int mid=l+(r-l)/2;            dfs(-1,1,mid);            if(jude())r=mid;            else l=mid+1;        }        if(l>m)printf("-1\n");        else  printf("%d\n",l);    }    return 0;}

 


联系
我们