「NOIP模拟赛」警察叔叔就是这个人！
题目背景
十个地方十人十色
全部都是猥琐大叔
这里也是那里也是
行踪可疑
现如今hentai横行，警察叔叔们不得不采取特♂殊手段惩戒这些家伙
题目描述
魅力之都是一个有N个路口，M条双向道路连接的城市。警察叔叔绘制了一张特殊的地图，在地图上只保留了N-1条道路，我们称这些道路为「特殊道路」，要保证任意两个路口间有且仅有一条路径，且满足所有保留的道路长度之和最小。
现在要在其中一个连接有多条「特殊道路」的路口设立「根据地」，去掉「根据地」所在路口后，就会出现某些路口间无法通过「特殊道路」相互连通的情况，我们认为这时仍然能够通过「特殊道路」连通的路口属于同一个「区域」。警察叔叔希望最后每个「区域」的「特殊道路」总长尽可能平均。警察叔叔找到了hzwer，但是hzwer是个无向图和有向图都无法区分的蒟蒻，请你帮他计算出应该选择哪一个路口作为「根据地」。
(尽可能平均即权值最小，设每一块「区域」的路线总长为Length[i]（包括连接「根据地」与该「区域」的边），平均路线长度为Avg=SUM{Length[i]}/区域数，权值d=∑ (Length[i]-Avg)^2
输入格式
第1行：2个正整数N,M
第2..M+1行：每行2个整数u,v和1个实数len，表示u,v之间存在长度为len的边
输出格式
第1行：1个整数，最后选择的路口编号（存在多个可选路口时选择编号小的）
样例数据 1
输入
3 3
3 1 5
3 2 4
1 2 3
输出
2
样例数据 2
输入
3 3
2 1 825.7291
3 2 397.4120
1 3 633.1370
输出
3
备注
对于60%的数据：3 ≤ N ≤ 2,000，N-1 ≤ M ≤ 50,000
对于100%的数据：3 ≤ N ≤ 40,000，N-1 ≤ M ≤ 200,000
对于100%的数据：0 < len ≤ 100,000,000
保证不存在相同距离的线路，两个路口间可能出现多条路径，且任意点对间至少存在一条路径
题解
题目大意
给定一个无向有权图,首先一个最小生成树 MST,从 MST 中选取一个度数大于 1 的点 作为根 K,使每颗子树及该子树到根的边权之和方差最小。输出 K 和最小方差的值。
考察算法最小生成树 树的遍历
算法1
首先毫无疑问的需要用到求最小生成树的算法,我们考虑使用 Kruskal 算法或是Prim 算法。求出最小生成树以后,依次枚举每一个点作为根进行遍历,取出其中的最小方差即可。
时间复杂度:O(MlogM+N^2)
期望得分:60
算法2
由于后 40%的数据 N 比较大,所以只能通过 Kruskal 算法求出最小生成树,接下来任选一个点作为根,进行一次遍历。记录 w[i]表示以 i 点作为根的子树的边权之和。 然后依次枚举每一个点 i,该点的子树权值可以直接求出,而以它父亲作为根的子树需要特殊处理。这颗特殊子树的权值为最小生成树总权值减去该点权值 w[i]。然后计算出方差,最后选取所有点当中最小方差的那个点即可。
时间复杂度:O(MlogM+N)
期望得分:100
本题来自东方系列模拟赛stage3
真的不是我懒得写代码。。
我的代码被我手贱删了，那我做个搬运工好了。。。
暴力：
|
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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
/* PROG: mokou AUTH: Nettle STAT: 60 */ #include <iostream> #include <vector> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> using namespace std; #define MAXN 50009 #define MAXE 200009 #define pb(x) push_back(x) #define mk(x, y) make_pair(x, y) struct EDGE { int u, v; double length; } edge[ MAXE ]; int N, edgecnt; struct Tree { vector< pair<int, double> > fir[ MAXN ]; double Sum, w[ MAXN ]; bool vis[ MAXN ]; void Addedge(int u, int v, double length) { Sum += length; fir[u].pb( mk(v, length) ); fir[v].pb( mk(u, length) ); return ; } void DFS(int now) { vis[ now ] = true; w[ now ] = 0; for (int i = 0; i != fir[now].size(); i++) if (!vis[ fir[now][i].first ]) { DFS( fir[now][i].first ); w[now] += fir[now][i].second + w[ fir[now][i].first ]; } return ; } void GetAns() { int best(-1); double best_ans(0), tp(0), Avg(0); for (int i = 1; i <= N; i++) if (fir[i].size() > 1) { memset(vis, 0, sizeof(vis)); DFS(i); tp = 0; Avg = Sum / fir[i].size(); for (int j = 0; j != fir[i].size(); j++) tp += (Avg - fir[i][j].second - w[ fir[i][j].first ]) * (Avg - fir[i][j].second - w[ fir[i][j].first ]); if (best == -1 || tp < best_ans) best_ans = tp, best = i; } printf("%d\n", best); return ; } } MST; struct Kruskal { int path[ MAXN ]; int Find(int x) { if (x != path[x]) path[x] = Find( path[x] ); return path[x]; } void Input() { scanf("%d %d", &N, &edgecnt); for (int i = 1; i <= edgecnt; i++) scanf("%d %d %lf", &edge[i].u, &edge[i].v, &edge[i].length); return ; } void Work() { int cnt(1), x, y; for (int i = 1; i <= N; i++) path[i] = i; for (int i = 1; i <= edgecnt && cnt < N; i++) { x = Find( edge[i].u ); y = Find( edge[i].v ); if (path[x] == path[y]) continue; path[x] = path[y]; MST.Addedge(edge[i].u, edge[i].v, edge[i].length); ++cnt; } return ; } } Kruskal; bool Comp(EDGE x, EDGE y) { return x.length < y.length; } int main() { Kruskal.Input(); sort(edge + 1, edge + edgecnt + 1, Comp); Kruskal.Work(); MST.GetAns(); return 0; } |
正解
|
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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
/* PROG: mokou AUTH: Nettle STAT: AC */ #include <iostream> #include <vector> #include <stdio.h> #include <stdlib.h> #include <algorithm> using namespace std; #define MAXN 50009 #define MAXE 200009 #define pb(x) push_back(x) #define mk(x, y) make_pair(x, y) struct EDGE { int u, v; double length; } edge[ MAXE ]; int N, edgecnt; struct Tree { vector< pair<int, double> > fir[ MAXN ]; double Sum, w[ MAXN ]; int path[ MAXN ]; bool vis[ MAXN ]; void Addedge(int u, int v, double length) { Sum += length; fir[u].pb( mk(v, length) ); fir[v].pb( mk(u, length) ); return ; } void DFS(int now) { vis[ now ] = true; for (int i = 0; i != fir[now].size(); i++) if (!vis[ fir[now][i].first ]) { path[ fir[now][i].first ] = now; DFS( fir[now][i].first ); w[now] += fir[now][i].second + w[ fir[now][i].first ]; } return ; } void GetAns() { int best(-1); double best_ans(0), tp(0), Avg(0); DFS(1); for (int i = 1; i <= N; i++) if (fir[i].size() > 1) { tp = 0; Avg = Sum / fir[i].size(); for (int j = 0; j != fir[i].size(); j++) if (fir[i][j].first != path[i]) tp += (Avg - fir[i][j].second - w[ fir[i][j].first ]) * (Avg - fir[i][j].second - w[ fir[i][j].first ]); else tp += (Avg - (Sum - w[i])) * (Avg - (Sum - w[i])); if (best == -1 || tp < best_ans) best_ans = tp, best = i; } printf("%d\n", best); return ; } } MST; struct Kruskal { int path[ MAXN ]; int Find(int x) { if (x != path[x]) path[x] = Find( path[x] ); return path[x]; } void Input() { scanf("%d %d", &N, &edgecnt); for (int i = 1; i <= edgecnt; i++) scanf("%d %d %lf", &edge[i].u, &edge[i].v, &edge[i].length); return ; } void Work() { int cnt(1), x, y; for (int i = 1; i <= N; i++) path[i] = i; for (int i = 1; i <= edgecnt && cnt < N; i++) { x = Find( edge[i].u ); y = Find( edge[i].v ); if (path[x] == path[y]) continue; path[x] = path[y]; MST.Addedge(edge[i].u, edge[i].v, edge[i].length); ++cnt; } return ; } } Kruskal; bool Comp(EDGE x, EDGE y) { return x.length < y.length; } int main() { Kruskal.Input(); sort(edge + 1, edge + edgecnt + 1, Comp); Kruskal.Work(); MST.GetAns(); return 0; } |
OI 课件=>
