初中毕业学网站开发工程师,中山有网站建设公司吗,深汕特别合作区天气预报,页面跳转流程图题目链接: http://www.51nod.com/onlineJudge/questionCode.html#!problemId1307 题意: 题解: 方法一#xff1a; 因为所有绳子最终组成了1棵树#xff0c;所以我们可以通过一次DFS#xff0c;来检测是否有某根绳子下面绑了超过他所能负荷的重量。 具体方法#xff1a;对… 题目链接: http://www.51nod.com/onlineJudge/questionCode.html#!problemId1307 题意: 题解: 方法一 因为所有绳子最终组成了1棵树所以我们可以通过一次DFS来检测是否有某根绳子下面绑了超过他所能负荷的重量。 具体方法对每个节点计算其子树的重量和包含自身的重量如果大于能承受的最大重量则绳子会断否则不会断。 一次DFS时间复杂度是O(n)的。 既然一次判断的复杂度是O(n)的并且当绳子第一次断掉后继续放重物不会改变绳子断掉的状态毕竟重物的重量都是正数没有负数那么我们可以用二分来做。 二分来求第一次断掉的点由于二分的复杂度是log(n)一次DFS判断的复杂度是O(n)所以整个算法的复杂度是nlog(n)。 二分经常被用来求解一些具有单调性的问题这里的单调性就是断掉以后不会再次变成不断的。 方法二 我们在DFS的过程中使用并查集将子树节点的Root指向当前节点同时计算子树的总重量。 假如当前节点的承重不足那么绳子会断掉。所以我们需要去掉一些节点来保证绳子不断。根据题目要求我们按照子树节点的编号从高到低逐个去掉这些重物直到绳子不断为止。 那么问题来了并查集这个结构并不能解决按照编号从高到低去掉子树的问题如果自己维护其他的数据结构比如堆恐怕复杂度还要多一个Log。 所以我们跳出按照编号从高到低去掉子树的思路不如直接从编号N - 1到0去掉子树直到当前的绳子不断为止。 因为编号小的断了后面再加的绳子也没有用了已经有绳子断了就结束了。 代码: 二分 1 #include bits/stdc.h2 using namespace std;3 typedef long long ll;4 #define MS(a) memset(a,0,sizeof(a))5 #define MP make_pair6 #define PB push_back7 const int INF 0x3f3f3f3f;8 const ll INFLL 0x3f3f3f3f3f3f3f3fLL;9 inline ll read(){
10 ll x0,f1;char chgetchar();
11 while(ch0||ch9){if(ch-)f-1;chgetchar();}
12 while(ch0ch9){xx*10ch-0;chgetchar();}
13 return x*f;
14 }
15 //
16 const int maxn 1e510;
17
18 struct node{
19 int c,w,f;
20 }e[maxn];
21
22 vectorint g[maxn];
23
24 bool book;
25
26 ll dfs(int u,int k){
27 ll sum e[u].w;
28 if(u k) return 0;
29 for(auto v : g[u])
30 sum dfs(v,k);
31 if(sum e[u].c u) book false;
32 return sum;
33 }
34
35 int main(){
36 int nread();
37 for(int i1; in; i){
38 e[i].cread(); e[i].wread(); e[i].fread(); e[i].f;
39 g[e[i].f].push_back(i);
40 }
41
42 int l0,rn,ans 0;
43 while(lr){
44 int mid (lr)/2;
45 book true;
46 dfs(0,mid);
47 if(book) ansmid,lmid1;
48 else rmid-1;
49 }
50
51 cout ans endl;
52
53 return 0;
54 } 并查集 1 #include bits/stdc.h2 using namespace std;3 typedef long long ll;4 #define MS(a) memset(a,0,sizeof(a))5 #define MP make_pair6 #define PB push_back7 const int INF 0x3f3f3f3f;8 const ll INFLL 0x3f3f3f3f3f3f3f3fLL;9 inline ll read(){
10 ll x0,f1;char chgetchar();
11 while(ch0||ch9){if(ch-)f-1;chgetchar();}
12 while(ch0ch9){xx*10ch-0;chgetchar();}
13 return x*f;
14 }
15 //
16 const int maxn 1e510;
17
18 struct node{
19 ll c,w,f;
20 }e[maxn];
21
22 vectorint g[maxn];
23 int fa[maxn];
24 ll ww[maxn];
25 int k;
26
27 int find(int x){
28 return fa[x]x ? x : fa[x]find(fa[x]);
29 }
30
31 void update(int u){
32 for(auto v : g[u]){
33 e[u].w e[v].w;
34 fa[v] u;
35 }
36
37 while(e[u].w e[u].c){
38 e[find(k)].w - ww[k];
39 k--;
40 }
41 }
42
43 int main(){
44 int nread();
45 for(int i1; in; i){
46 e[i].cread(); e[i].wread(); e[i].fread(); e[i].f;
47 g[e[i].f].push_back(i); ww[i] e[i].w;
48 fa[i] i;
49 }
50
51 k n;
52 for(int in; i0; i--)
53 update(i);
54
55 cout k endl;
56
57 return 0;
58 } 转载于:https://www.cnblogs.com/yxg123123/p/6827576.html
