本文共 928 字，大约阅读时间需要 3 分钟。
题意：
n个节点的通信连接树，切断每个边有一定的花费，要你切断边，在总花费不超过m的前提，使所有的其他节点都不能和节点1（根）连通，切边时有花费上限，让你最小化这个上限。
分析：最小化最大值，想到二分，二分上限求符合条件的总花费和m比较。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef pair 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=1<<20;const int mod = 1000000007;struct edge{ int t,w;};vector e[1010];int dp[1010],n,m,used[1010];void dfs(int root,int limit){ used[root]=1; int f=0,tmp=0; for(int i=0;i >1; dfs(1,mid); if(dp[1]<=m){r=mid-1;ff=mid;} else l=mid+1; } printf("%d\n",ff); }return 0;}
转载于:https://www.cnblogs.com/zsf123/p/4698972.html