An overview of the
Minimum spanning tree algorithm, that is, select N-1 edges in a weighted undirected graph with N points, so that each vertex is directly connected with each other and the weight sum is minimum. Such an algorithm is called minimum spanning tree algorithm (MST), which can be effectively solved by the classical Prim or Kruskal algorithm
But on the basis of this problem, if we want to figure out the sub-small grown tree, or the KTH small grown tree, how does this algorithm work?
Algorithm thought
The sub-minor spanning tree algorithm is based on the minimum spanning tree algorithm. First, we find the minimum spanning tree. Next, we enumerate each edge that is not on the MST and try to add this edge to the MST. According to the principle of MST, it can be thought that a ring must be formed, so that we take out the longest road in the loop (except the newly added edge). The result must be a smaller tree
The general idea is: enumeration plus edge -> must be a ring -> remove the longest edge in the ring -> get the sub-small growing tree
Algorithm implementation
Since it is built on the basis of MST, Prim or Kruskal algorithm can naturally achieve the sub-small growing tree, we will introduce below
Prim implementation
In the process of rewriting Prim, you need to define several arrays
Pre [I] : indicates the parent node of I. Maxd [I][j] : indicates the maximum value from I -> j in MSTCopy the codeMaxd [u][v]
must be two points on an edge. If maxd[u][v]
must be two points on an edge. If maxd[u][v]
must be two points on an edge
,>
,>
,>
Maxd [u][v] = maxd[u][v] = maxd[u][v
MaxD [u][v] = Max (maxD[pre[u]][v], d[u]) maxD[pre[u]][v], d[u]) Notice the two conditions for updating the equation,
must be two points on an edge, and u,v must both already be in MST
,v>
int N, M, w[maxn][maxn];
int d[maxn];
bool used[maxn];
int maxD[maxn][maxn]; //MST from I ->j maximum weight value
int pre[maxn]; // A point parent node
bool mst[maxn][maxn]; // Whether the point is already in the MST
typedef pair<int.int> P;
int Prim(int s) {
fill(d, d + maxn, inf);
ms(maxD, 0);
ms(used, 0);
ms(mst, 0);
fill(pre, pre + maxn, s);
priority_queue<P, vector<P>, greater<P> > q;
q.push(P(d[s] = 0, s));
int res = 0;
while(! q.empty()) {
P cur = q.top(a); q.pop(a);int u = cur.second;
if(used[u])
continue;
used[u] = true, res += d[u];
mst[u][pre[u]] = mst[pre[u]][u] = true; // Add to MST
for(int v = 1; v <= N; ++v) {
if(used[v] && w[u][v] < inf) // Update only MST
maxD[u][v] = maxD[v][u] = max(maxD[pre[u]][v], d[u]);
if(w[u][v] < d[v]) {
d[v] = w[u][v];
pre[v] = u; // Update the parent node
q.push(P(d[v], v)); }}}return res;
}
Copy the codeThe key here is to find the value of these arrays, as to the size of the tree or other related operations through the assistance of these arrays, it is very simple!
Kruskal implementation
In Kruskla algorithm, the edge weights enumerated by us will increase in turn, which will provide some convenience for us to update maxd. However, because the implementation of Kruskal is different from that of Prim, Kruskal needs to store the nodes in the current minimum span tree (adjacent matrix), and then we can update maxd array
Pay attention to a few details
- Here, because the parent node array shares and looks up the set’s PAR array, path compression cannot be used in Unite
- Directly operate on the parent node of U, and the parent node of V must still be V
#define ms(x, n) memset(x,n,sizeof(x));
typedef long long LL;
const int inf = 1 << 30;
const LL maxn = 110;
int N, M;
struct Edge {
int u, v, w;
} es[maxn * maxn];
int par[maxn], rak[maxn];
void init(int n) {
for(int i = 0; i <= n; i++)
par[i] = i, rak[i] = 0;
}
int findr(int x) {
if(x == par[x]) return x;
else return par[x] = findr(par[x]);
}
bool isSame(int x, int y) {return findr(x) == findr(y); }bool cmp(const Edge &a, const Edge &b) {returna.w < b.w; }int maxd[maxn][maxn]; // I ->j
bool used[maxn*maxn]; // Whether the change is already in the MST
vector<int> mst[maxn]; / / store the MST
void Kruskal(a) {
sort(es+1, es+1+M, cmp);
init(N);
ms(maxd, 0); ms(mst, 0); ms(used, 0);
for(int i = 0; i <= N; ++i)
mst[i].push_back(i);
int sum = 0;
for(int i = 1; i <= M; i++) {
int u = findr(es[i].u), v = findr(es[i].v), w = es[i].w;
if(!isSame(u, v)) {
sum += w, used[i] = true;
for(int j = 0; j < mst[u].size(a); ++j)for(int k = 0; k < mst[v].size(a); ++k) maxd[mst[u][j]][mst[v][k]] = maxd[mst[v][k]][mst[u][j]] = w; par[u] = v;for(int j = 0; j < mst[u].size(a); ++j) mst[v].push_back(mst[u][j]); // One-way storage is ok}}int csum = inf;
for(int i = 1; i <= M; ++i)
if(! used[i]) csum =min(csum, sum+es[i].w-maxd[es[i].u][es[i].v]);
cout << sum << "" << csum << endl;
}
Copy the codeExample 1
The Unique MST POJ – 1679
Once there were two cats. They really don’t know what to do.
Instead of healing, they started playing a game in which they deleted some of the existing roads from the town map, and the map was still connected. Among all the schemes, the scheme with the largest total road length deleted is the optimal one.
Both cats completed the game at the same time. They all believe they are the winner. Given that they are done in different ways, determine whether it is possible that they are all implemented optimally.
Input
The first line is an integer t (1 <= t <= 20), the number of test cases. Each use case represents a graph with the first row n and m (1 <= n <= 100) for the number of towns and the number of roads, respectively. Next, M acts as m triples (xi, yi, WI), indicating that towns numbered xi and yi are connected by roads of length WI. The two towns are connected by at most one road.
Output
For each use case, if the answer is no (that is, it cannot all be optimal), output the total length of the remaining (note not deleted) roads of the optimal solution. Otherwise output the string ‘Not Unique! ‘(without quotation marks).
Examples
Sample Input 2 3 3 1 2 1 2 3 2 3 1 3 4 4 1 2 2 2 3 2 3 4 2 4 1 2 Sample Output 3 Not Unique!
The question:
Determine whether the minimum spanning tree and the secondary spanning tree are equal. If they are equal, output Not Unique!
Answer key:
Here we use the template just now, directly insert Prim to determine whether the edge weight added to MST is equal to maxd of the current edge. If it is equal, it means that there must be a sub-small tree equal to MST; Ssum ==sum
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef long long LL;
const int inf = 1<<30;
const LL maxn = 110;
int N, M, w[maxn][maxn];
int d[maxn];
bool used[maxn];
int maxD[maxn][maxn]; //MST from I ->j maximum weight value
int pre[maxn]; // A point parent node
bool mst[maxn][maxn]; // Whether the point is already in the MST
typedef pair<int.int> P;
int Prim(int s){
fill(d, d+maxn, inf); ms(maxD, 0);
ms(used, 0); ms(mst, 0);
fill(pre, pre+maxn, s);
priority_queue<P, vector<P>, greater<P> > q;
q.push(P(d[s]=0, s));
int res = 0;
while(! q.empty()){
P cur = q.top(a); q.pop(a);int u = cur.second;
if(used[u]) continue;
used[u] = true, res += d[u];
mst[u][pre[u]] = mst[pre[u]][u] = true; // Add to MST
for(int v = 1; v <= N; ++v){
if(used[v] && w[u][v]<inf) // Update only MST
maxD[u][v] = maxD[v][u] = max(maxD[pre[u]][u], d[u]);
if(w[u][v] < d[v]){
d[v] = w[u][v];
pre[v] = u; // Update the parent node
q.push(P(d[v], v)); }}}return res;
}
int main(a)
{
int T, a, b, c;
cin >> T;
while(T--){
fill(w[0], w[0]+maxn*maxn, inf);
cin >> N >> M;
while(M--){
cin >> a >> b >> c;
w[a][b] = w[b][a] = c;
}
int ans = Prim(1);
bool flag = false; // Whether the smaller spanning tree is equal to the minimum spanning tree
for(int u = 1; u <= N && ! flag; ++u){for(int v = 1; v <= N; ++v){
if(mst[u][v] || w[u][v]==inf)
continue;
if(w[u][v] == maxD[u][v]){
flag = true;
break; }}}if(flag) cout << "Not Unique! \n";
else cout << ans << endl;
}
return 0;
}
Copy the codeExample 2
Qin Shi Huang’s National Road System HDU – 4081
During the Warring States Period of ancient China(476 BC to 221 BC), there were seven kingdoms in China —- they were Qi, Chu, Yan, Han, Zhao, Wei and Qin. Ying Zheng was the king of the kingdom Qin. Through 9 years of wars, he finally conquered all six other kingdoms and became the first emperor of a unified China in 221 BC. That was Qin dynasty —- the first imperial dynasty of China(not to be confused with the Qing Dynasty, the last dynasty of China). So Ying Zheng named himself “Qin Shi Huang” because “Shi Huang” means “the first emperor” in Chinese.
Qin Shi Huang undertook gigantic projects, including the first version of the Great Wall of China, the now famous city-sized mausoleum guarded by a life-sized Terracotta Army, and a massive national road system. There is a story about the road system: There were n cities in China and Qin Shi Huang wanted them all be connected by n-1 roads, in order that he could go to every city from the capital city Xianyang. Although Qin Shi Huang was a tyrant, he wanted the total length of all roads to be minimum,so that the road system may not cost too many people’s life. A daoshi (some kind of monk) named Xu Fu told Qin Shi Huang that he could build a road by magic and that magic road would cost no money and no labor. But Xu Fu could only build ONE magic road for Qin Shi Huang. So Qin Shi Huang had to decide where to build the magic road. Qin Shi Huang wanted the total length of all none magic roads to be as small as possible, but Xu Fu wanted the magic road to benefit as many people as possible —- So Qin Shi Huang decided that the value of A/B (the ratio of A to B) must be the maximum, which A is the total population of the two cites connected by the magic road, and B is the total length of none magic roads. Would you help Qin Shi Huang? A city can be considered as a point, and a road can be considered as a line segment connecting two points.
Input
The first line contains an integer t meaning that there are t test cases(t <= 10). For each test case: The first line is an integer n meaning that there are n cities(2 < n <= 1000). Then n lines follow. Each line contains three integers X, Y and P ( 0 <= X, Y <= 1000, 0 < P < 100000). (X, Y) is the coordinate of a city and P is the population of that city. It is guaranteed that each city has a distinct location.
Output
For each test case, print a line indicating the above mentioned maximum ratio A/B. The result should be rounded to 2 digits after decimal point.
Examples
Sample Output 2 4 1 1 20 1 2 30 200 2 80 200 1 100 3 1 1 20 1 2 30 2 2 40 Sample Output 65.00 70.00
The question:
Given the coordinates of N points and the population of each point, it is required to connect these N points through n-1 edge. The weight is the direct distance between the two points; B is the sum of the distance; at the same time, an edge can be selected so that the weight of the edge becomes 0 and A is the population of the two points on the edge. I want to maximize A over B
Answer key:
(ans = Max (ans, A/(b-w [I][j]))); (ans = Max (ans, A/(b-w [I][j]))); (ans = Max (ans, A/(b-w [I][j])))); If ans = Max (A/(b-maxd [I][J]));
As you can see, even though I’m not using the subminor tree directly, I’m using all of the arrays that the subminor tree gives me, which is why I didn’t do the subminor tree directly, because most of the problems are not necessarily naked, so it’s important to understand the idea of subminor tree, right
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef long long LL;
const int inf = 1 << 30;
const LL maxn = 1010;
int N;
double w[maxn][maxn];
struct node {
int x, y;
int p;
node(int xx, int yy, intpp) {x = xx, y = yy, p = pp; }node() {}
} vs[maxn];
double getDis(int x1, int y1, int x2, int y2) {
return sqrt((double)(x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}
double d[maxn];
bool used[maxn];
double maxD[maxn][maxn]; //MST from I ->j maximum weight value
int pre[maxn]; // A point parent node
bool mst[maxn][maxn]; // Whether the point is already in the MST
typedef pair<int.int> P;
double Prim(int s) {
fill(d, d + maxn, inf);
fill(pre, pre+maxn, s);
ms(maxD, 0); ms(used, 0); ms(mst, 0);
priority_queue<P, vector<P>, greater<P> > q;
q.push(P(d[s] = 0, s));
double res = 0;
while(! q.empty()) {
P cur = q.top(a); q.pop(a);int u = cur.second;
if(used[u])
continue;
used[u] = true, res += d[u];
mst[u][pre[u]] = mst[pre[u]][u] = true; // Add to MST
for(int v = 1; v <= N; ++v) {
if(used[v] && w[u][v] < inf) // Update only MST
maxD[u][v] = maxD[v][u] = max(maxD[pre[u]][v], d[u]);
if(w[u][v] < d[v]) {
d[v] = w[u][v];
pre[v] = u; // Update the parent node
q.push(P(d[v], v)); }}}return res;
}
int main(a) {
int T, a, b, c;
scanf("%d",&T);
while(T--) {
ms(vs, 0); fill(w[0], w[0]+maxn*maxn, inf);
scanf("%d",&N);
for(int i = 1; i <= N; ++i) {
scanf("%d%d%d",&a,&b,&c);
vs[i] = node(a, b, c);
}
for(int i = 1; i < N; ++i)
for(int j = i+1; j <= N; ++j)
w[i][j] = w[j][i] = getDis(vs[i].x, vs[i].y, vs[j].x, vs[j].y);
// Enumerates the edges to find the maximum value
double B = Prim(1), A, ans = - 1;
for(int i = 1; i < N; ++i)
for(int j = i+1; j <= N; ++j){
A = vs[i].p+vs[j].p;
// If this edge is not used in MST, try adding an edge and deleting the longest edge in the generation ring. If it is used, change it to 0
if(mst[i][j]){
ans = max(ans, A/(B-w[i][j]));
}else{
ans = max(ans, A/(B-maxD[i][j])); }}printf("%.2lf\n", ans);
}
return 0;
}
Copy the code