首页 > 代码库 > HDU 3586 Information Disturbing (二分+树形dp)

HDU 3586 Information Disturbing (二分+树形dp)

2024-08-14 05:53:07   219人阅读

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

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

dp[i]表示i节点为root的这个子树所破坏的最少费用，if(cost[i][i->son] <= limit) dp[i] += min(dp[i->son], cost[i][i->son]);

二分limit，然后把limit放到dfs中判断是不是都能切断叶子节点的联系。

 1 #pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 typedef pair <int, int> P;16 const int N = 1e5 + 5;17 int to[N << 1], Next[N << 1], cost[N << 1], head[N], tot, dp[N], inf = 1e6 + 7;18 19 void init() {20     memset(head, -1, sizeof(head));21     tot = 0;22 }23 inline void add_edge(int u, int v, int c) {24     Next[tot] = head[u];25     to[tot] = v;26     cost[tot] = c;27     head[u] = tot++;28 }29 void dfs(int u, int p, int limit) {30     dp[u] = inf;31     bool inter = false;32     for(int i = head[u]; ~i; i = Next[i]) {33         int v = to[i];34         if(v == p)35             continue;36         dfs(v, u, limit);37         if(!inter) {38             dp[u] = 0;39             inter = true;40         }41         if(cost[i] <= limit) {42             dp[u] += min(dp[v], cost[i]);43         } else {44             dp[u] += dp[v];45         }46     }47 }48 void solve() {49     int n, m, u, v, c;50     while(~scanf("%d %d", &n, &m) && (n || m)) {51         init();52         for(int i = 1; i < n; ++i) {53             scanf("%d %d %d", &u, &v, &c);54             add_edge(u, v, c);55             add_edge(v, u, c);56         }57         int l = 1, r = 1001;58         while(l < r) {59             int mid = (l + r) >> 1;60             dfs(1, -1, mid);61             if(dp[1] <= m) {62                 r = mid;63             } else {64                 l = mid + 1;65             }66         }67         if(r == 1001) {68             printf("-1\n");69         } else {70             printf("%d\n", l);71         }72     }73 }74 75 int main()76 {77     solve();78     return 0;79 }

 

HDU 3586 Information Disturbing (二分+树形dp)


联系
我们