【构造+DFS】2017多校训练三 HDU 6060 RXD and dividing

acm.hdu.edu.cn/showproblem.php?pid=6060

【题意】

给定一棵以1为根的树，把这颗树除1以外的结点划分为k个集合（可以有空集），把1加入划分后的集合
每个集合的结点形成一棵最小生成树
所有最小生成树的权值之和最大化

【思路】

最小生成树，每个点u到root 1都要有唯一的一条路径，那么显然，u到1沿路的每条边贡献都为1
现在考虑每条边的贡献
对于某条边uv,v是离根更远的结点，以v为根的子树大小为sz[v],显然我们可以通过把sz[v]个结点划分到sz[v]个不同的集合中，使得uv的贡献为sz[v]
当然，sz[v]大于k时我们只能取k

【Accepted】

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<stack>
 9 #include<map>
10 #include<vector> 
11 using namespace std;
12 typedef long long ll;
13 int n,k;
14 const int maxn=2e6+3;
15 struct node
16 {
17     int v;
18     ll c;
19     node(int _v,ll _c):v(_v),c(_c){}
20 };
21 vector<node> vec[maxn];
22 ll ans;
23 int sz[maxn];
24 int DFS(int u,int pa)
25 {
26     sz[u]=1;
27     for(int i=0;i<vec[u].size();i++)
28     {
29         int v=vec[u][i].v;
30         if(v==pa) continue;
31         sz[u]+=DFS(v,u);
32         ll cnt=min(sz[v],k);
33         ans+=vec[u][i].c*cnt;
34     }
35     return sz[u];
36 }
37 int main()
38 {
39     while(scanf("%d%d",&n,&k)!=EOF)
40     {
41         for(int i=0;i<maxn;i++)
42         {
43             vec[i].clear();
44         }
45         memset(sz,0,sizeof(sz));
46         for(int i=0;i<n-1;i++)
47         {
48             int u,v;
49             ll c;
50             scanf("%d%d%lld",&u,&v,&c);
51             vec[u].push_back(node(v,c));
52             vec[v].push_back(node(u,c));
53         }
54         ans=0ll;
55         DFS(1,-1); 
56         printf("%lld
",ans);
57     }
58     return 0;
59 }

vector注意多组数据要清空

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<stack>
 9 #include<map>
10 #include<vector> 
11 using namespace std;
12 typedef long long ll;
13 int n,k;
14 const int maxn=2e6+3;
15 struct edge
16 {
17     int to;
18     int nxt;
19     ll c;
20 }e[maxn];
21 ll ans;
22 int sz[maxn];
23 int head[maxn];
24 int tot;
25 void init()
26 {
27     memset(head,-1,sizeof(head));
28     memset(sz,0,sizeof(sz));
29     tot=0;
30 }
31 
32 void add(int u,int v,ll c)
33 {
34     e[tot].to=v;
35     e[tot].nxt=head[u];
36     e[tot].c=c;
37     head[u]=tot++;
38 }
39 
40 int DFS(int u,int pa)
41 {
42     sz[u]=1;
43     for(int i=head[u];i!=-1;i=e[i].nxt)
44     {
45         int v=e[i].to;
46         ll c=e[i].c;
47         if(v==pa) continue;
48         sz[u]+=DFS(v,u);
49         ll cnt=min(sz[v],k);
50         ans+=cnt*c;
51     }
52     return sz[u];
53 }
54 int main()
55 {
56     while(scanf("%d%d",&n,&k)!=EOF)
57     {
58         init();
59         for(int i=0;i<n-1;i++)
60         {
61             int u,v;
62             ll c;
63             scanf("%d%d%lld",&u,&v,&c);
64             add(u,v,c);
65             add(v,u,c);
66         }
67         ans=0;
68         DFS(1,-1);
69         printf("%lld
",ans);
70     }
71     return 0;
72 }

邻接表双向边注意边数要1e6*2

【注意事项】

多组数据vector要清空，不然会wa而且stackoverflow
双向边要开两倍的数组，不然会RE