#include<bits/stdc++.h> usingnamespace std; int n,m,cnt,flag,px,py,ans,f[10000]; structp { int x,y,z; }a[250008]; intfind(int x){ if (x==f[x]) return x; return f[x]=find(f[x]); } boolcmp(p a,p b){ return a.z<b.z; } intmain(){ cin>>n>>m; for (int i=0;i<=m;i++) f[i]=i; //并查集初始化 for (int i=1;i<=m;i++) { cnt++; a[cnt].x=0; a[cnt].y=i; a[cnt].z=n; } //每一个都可以单独购买就是说 for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) { cin>>falg; if (flag){ cnt++; a[cnt].x=i; a[cnt].y=j; a[cnt].z=flag; } } //这个就是优惠的，买了i就可以把j也并进去。 sort(a+1,a+cnt+1,cmp); //排序，保证算法正确性 for (int i=1;i<=cnt;i++) { px=find(a[i].x); //找x的祖先 py=find(a[i].y); //找y的祖先 if (px==py) continue; f[px]=py; //赋值祖先 ans+=a[i].z; //统计答案 } cout<<ans; //输出答案 }
[BJWC2010] 严格次小生成树
题目描述
小 C 最近学了很多最小生成树的算法，Prim 算法、Kruskal
算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P
说，让小 C
求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是
\(E_M\)，严格次小生成树选择的边集是
\(E_S\)，那么需要满足：(\(value(e)\) 表示边 \(e\) 的权值) \(\sum_{e \in E_M}value(e)<\sum_{e \in
E_S}value(e)\)。
对于 \(30\%\) 的数据，\(1 \le n < 1000\)，\(1 \le m < 10,000\)，\(1\le q< 1000\)；
对于 \(60\%\) 的数据，\(1 \le n < 1000\)，\(1 \le m < 5\times 10^4\)，\(1 \le q< 1000\)；
对于 \(100\%\) 的数据，\(1 \le n < 10^4\)，\(1 \le m < 5\times 10^4\)，$1 q< 3^4
$，\(0 \le z \le 10^5\)。
本题思路：
在最大生成树上找一条最小边，实现的过程就是在最大生成树上跑倍增LCA。
我们就要单独把最大生成树建好（除去多余边），所以我们就需要在Kruskal的时候直接建树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
voidkruskal() { sort(edge + 1, edge + 1 + m, cmp); for (int i = 1; i <= n; i ++ ) { fa[i] = i; } for (int i = 1; i <= m; i ++ ) { int fx = find(edge[i].x); int fy = find(edge[i].y); if (fx != fy) { fa[fx] = fy; add(edge[i].x, edge[i].y, edge[i].val); add(edge[i].y, edge[i].x, edge[i].val); } } }
DFS做几个处理：
1.处理出每个点的深度（LCA）
2.处理好每个点的上1个点（LCA）
3.处理好每个点到它的上一个点的距离（LCA边权）
1 2 3 4 5 6 7 8 9 10 11 12 13
voiddfs(int x) { for (int i = head[x]; i; i = nex[i]) { int y = to[i]; if (deep[y]) continue ; deep[y] = deep[x] + 1; f[y][0] = x; w[y][0] = val[i]; dfs(y); } }
intlca(int x, int y) { if (find(x) != find(y)) return-1; int ans = inf; if (deep[x] > deep[y]) swap(x, y); for (int i = 20; i >= 0; i -- ) { if (deep[f[y][i]] >= deep[x]) { ans = min(ans, w[y][i]); y = f[y][i]; } } if (x == y) return ans; for (int i = 20; i >= 0; i -- ) { if (f[x][i] != f[y][i]) { ans = min(ans, min(w[x][i], w[y][i])); y = f[y][i]; x = f[x][i]; } } ans = min(ans, min(w[x][0], w[y][0])); return ans; }
int fa[MAXN], deep[MAXN], f[MAXN][21], w[MAXN][21];
int tot, to[MAXM], val[MAXM], nex[MAXM], head[MAXN];
struct Edge { int x, y, val; } edge[MAXM]; //存边
bool cmp(Edge a, Edge b) { return a.val > b.val; } //排序，最大生成树
int find(int x) { if (fa[x] == x) return x; return fa[x] = find(fa[x]); } //并查集查找
void add(int x, int y, int z) { to[++tot] = y; val[tot] = z; nex[tot] = head[x]; head[x] = tot; } //链式前向星添树边
void kruskal() { sort(edge + 1, edge + 1 + m, cmp); for (int i = 1; i <= n; i++) { fa[i] = i; } for (int i = 1; i <= m; i++) { int fx = find(edge[i].x); int fy = find(edge[i].y); if (fx != fy) { fa[fx] = fy; add(edge[i].x, edge[i].y, edge[i].val); add(edge[i].y, edge[i].x, edge[i].val); } } } //跑最大生成树，不解释
void dfs(int x) { for (int i = head[x]; i; i = nex[i]) { int y = to[i]; if (deep[y]) continue; deep[y] = deep[x] + 1; //深度+1 f[y][0] = x; //父节点 w[y][0] = val[i]; //距离 dfs(y); //开搜 } }
int lca(int x, int y) { if (find(x) != find(y)) return -1; //不在那一条线上 int ans = inf; if (deep[x] > deep[y]) swap(x, y); //保证y深 for (int i = 20; i >= 0; i--) { if (deep[f[y][i]] >= deep[x]) { ans = min(ans, w[y][i]); y = f[y][i]; } } //跳Y if (x == y) return ans; //直接返回 for (int i = 20; i >= 0; i--) { if (f[x][i] != f[y][i]) { ans = min(ans, min(w[x][i], w[y][i])); y = f[y][i]; x = f[x][i]; } } //跳x,y ans = min(ans, min(w[x][0], w[y][0])); //和根节点比一下 return ans; }
int main() { cin>>n>>m; for (int i = 1; i <= m; i++) { cin>>edge[i].x>>edge[i].y>>edge[i].val; } kruskal(); cin>>q; for (int i = 1; i <= n; i++) { if (!deep[i]) { deep[i] = 1; dfs(i); f[i][0] = i; w[i][0] = inf; //节点很高，父节点是自己 } } for (int i = 1; i <= 20; i++) { for (int j = 1; j <= n; j++) { f[j][i] = f[f[j][i - 1]][i - 1]; w[j][i] = min(w[j][i - 1], w[f[j][i - 1]][i - 1]); } } //预处理一下倍增 for (int i = 1; i <= q; i++) { int x, y; cin>>x>>y; cout<<lca(x, y)<<'\n'; //开始lca跳了 } return 0; }
Shichikuji is the new resident deity of the South Black Snail Temple.
Her first job is as follows:
There are $ n $ new cities located in Prefecture X. Cities are
numbered from $ 1 $ to $ n $ . City $ i $ is located $ x_i $ km North of
the shrine and $ y_i $ km East of the shrine. It is possible that $
(x_i, y_i) = (x_j, y_j) $ even when $ i j $ .
Shichikuji must provide electricity to each city either by building a
power station in that city, or by making a connection between that city
and another one that already has electricity. So the City has
electricity if it has a power station in it or it is connected to a City
which has electricity by a direct connection or via a chain of
connections.
Building a power station in City $ i $ will cost $ c_i $ yen;
Making a connection between City $ i $ and City $ j $ will cost $
k_i + k_j $ yen per km of wire used for the connection. However, wires
can only go the cardinal directions (North, South, East, West). Wires
can cross each other. Each wire must have both of its endpoints in some
cities. If City $ i $ and City $ j $ are connected by a wire, the wire
will go through any shortest path from City $ i $ to City $ j $ . Thus,
the length of the wire if City $ i $ and City $ j $ are connected is $
|x_i - x_j| + |y_i - y_j| $ km.
Shichikuji wants to do this job spending as little money as possible,
since according to her, there isn't really anything else in the world
other than money. However, she died when she was only in fifth grade so
she is not smart enough for this. And thus, the new resident deity asks
for your help.
And so, you have to provide Shichikuji with the following
information: minimum amount of yen needed to provide electricity to all
cities, the cities in which power stations will be built, and the
connections to be made.
If there are multiple ways to choose the cities and the connections
to obtain the construction of minimum price, then print any of them.
输入格式
First line of input contains a single integer $ n $ ( $ 1 n $ ) — the
number of cities.
Then, $ n $ lines follow. The $ i $ -th line contains two
space-separated integers $ x_i $ ( $ 1 x_i ^6 $ ) and $ y_i $ ( $ 1 y_i
^6 $ ) — the coordinates of the $ i $ -th city.
The next line contains $ n $ space-separated integers $ c_1, c_2, ,
c_n $ ( $ 1 c_i ^9 $ ) — the cost of building a power station in the $ i
$ -th city.
The last line contains $ n $ space-separated integers $ k_1, k_2, ,
k_n $ ( $ 1 k_i ^9 $ ).
输出格式
In the first line print a single integer, denoting the minimum amount
of yen needed.
Then, print an integer $ v $ — the number of power stations to be
built.
Next, print $ v $ space-separated integers, denoting the indices of
cities in which a power station will be built. Each number should be
from $ 1 $ to $ n $ and all numbers should be pairwise distinct. You can
print the numbers in arbitrary order.
After that, print an integer $ e $ — the number of connections to be
made.
Finally, print $ e $ pairs of integers $ a $ and $ b $ ( $ 1 a, b n $
, $ a b $ ), denoting that a connection between City $ a $ and City $ b
$ will be made. Each unordered pair of cities should be included at most
once (for each $ (a, b) $ there should be no more $ (a, b) $ or $ (b, a)
$ pairs). You can print the pairs in arbitrary order.
If there are multiple ways to choose the cities and the connections
to obtain the construction of minimum price, then print any of them.
样例 #1
样例输入 #1
1 2 3 4 5 6
3 2 3 1 1 3 2 3 2 3 3 2 3
样例输出 #1
1 2 3 4
8 3 1 2 3 0
样例 #2
样例输入 #2
1 2 3 4 5 6
3 2 1 1 2 3 3 23 2 23 3 2 3
样例输出 #2
1 2 3 4 5 6
27 1 2 2 1 2 2 3
提示
For the answers given in the samples, refer to the following diagrams
(cities with power stations are colored green, other cities are colored
blue, and wires are colored red):
For the first example, the cost of building power stations in all
cities is $ 3 + 2 + 3 = 8 $ . It can be shown that no configuration
costs less than 8 yen.
For the second example, the cost of building a power station in City
2 is 2. The cost of connecting City 1 and City 2 is $ 2 (3 + 2) = 10 $ .
The cost of connecting City 2 and City 3 is $ 3 (2 + 3) = 15 $ . Thus
the total cost is $ 2 + 10 + 15 = 27 $ . It can be shown that no
configuration costs less than 27 yen.
#include<bits/stdc++.h> using ll = longlong; #define rep(i, a, b) for (int i = a; i <= b; i++) #define frep(i, a, b) for (int i = a; i >= b; i--) usingnamespace std; constint MX = 100010; int N, M, k, aa = 0, es = 0, fa[MX], cnt = 0; structEdge { int x, y; }; // 存边 structnode { int x, y, z; } Ans[MX]; // 存答案 Edge wa[MX], er[MX]; // 水泥，鹅卵石 bool vis[MX]; // 判断 intfind(int x) { if (fa[x] == x) return x; return fa[x] = find(fa[x]); } // 并查集判断 voidkrus1() { memset(vis, 0, sizeof vis); // 清空 // 解释一下这一编最小生成树的意义 //找到那些必须加入的0边 int tot = 0, num = 0; // 开始跑 rep(i, 1, N) fa[i] = i; // 初始化 rep(i, 1, aa) { int a = find(wa[i].x); int b = find(wa[i].y); if (a != b) { fa[a] = b; // 赋值 tot++; // 加水泥路 } } rep(i, 1, es) { int a = find(er[i].x); int b = find(er[i].y); if (a != b) { vis[i] = 1; tot++; // 继续加鹅卵石路 num++; // 记录数量 fa[a] = b; // 赋值 if (tot == N - 1) break; // 够了，休息罢 } } if (tot < N - 1 || num > k) { // 不能加到N-1条或者要加的鹅卵石路很多，直接走 puts("no solution"); exit(0); } return; } //这一遍则是找到k条相邻的边后，进行找水泥路 voidkrus2() { int tot = 0; rep(i, 1, N) fa[i] = i; rep(i, 1, es) { if (vis[i] == 0) continue; if (tot == k) break; int a = find(er[i].x); int b = find(er[i].y); if (a != b) { Ans[++cnt] = (node){er[i].x, er[i].y, 0}; tot++; fa[a] = b; } } // 尽可能多的加水泥路 rep(i, 1, es) { if (tot == k) break; if (vis[i] == 1) continue; int a = find(er[i].x); int b = find(er[i].y); if (a != b) { Ans[++cnt] = (node){er[i].x, er[i].y, 0}; fa[a] = b; tot++; } } // 一定要到k条 if (tot < k) { cout << "no solution"; exit(0); } rep(i, 1, aa) { int a = find(wa[i].x); int b = find(wa[i].y); if (a != b) { tot++; fa[a] = b; Ans[++cnt] = (node){wa[i].x, wa[i].y, 1}; } } // 开始加上鹅暖石路 return; } intmain() { cin >> N >> M >> k; rep(i, 1, M) { int u, v, w; cin >> u >> v >> w; if (w == 1) wa[++aa].x = u, wa[aa].y = v; else er[++es].x = u, er[es].y = v; } krus1(); krus2(); rep(i, 1, cnt) cout << Ans[i].x << " " << Ans[i].y << ' ' << Ans[i].z << '\n'; return0; }
