Efficient Tracking
Efficient Tracking
CF Gym 101804E
这已经是一周前做的题目了，果然我真是能鸽善鹉。。。。
题目来源: Codeforces
分析
这题是很常规的一道题目，其实总体而言就是求最大生成树。不过在求完之后还需要再搜索一遍，然后以节点1为根节点建树即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge
{
trueint from,to,val;
trueEdge(int from=0,int to=0,int val=0):from(from),to(to),val(val) {}
trueconst bool operator < (const Edge &tmp)const{
truetruereturn val > tmp.val;
true}
}e[1000100];
struct Node
{
truevector<int> e;
}node[1010];
int fa[1010];
int anc[1010];
int find(int x)
{
truereturn x==fa[x]? x : fa[x] = find(fa[x]);
}
int dfs(int x)
{
truefor (int i = 0; i<node[x].e.size(); i++)
truetrueif (anc[node[x].e[i]]==0)
truetrue{
truetruetrueanc[node[x].e[i]] = x;
truetruetruedfs(node[x].e[i]);
truetrue}
}
int main()
{
trueint n;
truecin >> n;
truefor (int i = 1; i<=n; i++)
truetruefa[i] = i;
trueint num = 0;
truefor (int i = 2; i<=n; i++)
truetruefor (int j = 1; j<i; j++)
truetrue{
truetruetrueint x;
truetruetruecin >> x;
truetruetruee[++num] = Edge(i,j,x);
truetrue}
truesort(e+1,e+1+num);
truelong long ans = 0;
trueint cnt = 1;
truefor (int i = 1; i<=num; i++)
true{
truetrueint fx = find(e[i].from);
truetrueint fy = find(e[i].to);
truetrueif (fx!=fy)
truetrue{
truetruetruefa[fx] = fy;
truetruetruenode[e[i].from].e.push_back(e[i].to);
truetruetruenode[e[i].to].e.push_back(e[i].from);
truetruetrueans += e[i].val;
truetruetruecnt ++;
truetrue}
truetrueif (cnt==n)
truetruetruebreak;
true}
truedfs(1);
truecout << ans << endl;
truefor (int i = 2; i<=n; i++)
truetruecout << anc[i] << endl;
}
|