当前位置：网站首页>7.27 minimum spanning tree phased test problem solution
7.27 minimum spanning tree phased test problem solution
2022-07-28 09:56:00 【liuyanjia123】
One 、 Examination experience
1.T1 A new start
This question , At the beginning of the exam , At first glance, I thought about the positive solution , So I began to determine this idea The correctness of the , So I turned on the computer “ Painting third brother ” Tools , Start drawing （ The mouse is really hard to use , Be sure to bring draft paper next time ）, Just about to prove it , The one next to me likes “ Singing and dancing rap Of person（dog ）” He shouted in a low voice ：“ Oh , I got it! ！ This problem is to run the minimum spanning tree first , Plus the minimum cost of building a power station ”. This is a sentence of all evil , Broke all my thoughts , do not know why , It seems that inspiration is gone , The brain is blank （ The sky is clear , White clouds are floating in the sky ）, Unconsciously began to think about his practice . however , For a moment “sb ” I actually think this practice is right , therefore , I hung up 50 points for no reason .
I hung up this 50 branch , Tell us not to listen to others during the exam people The ghost of .
2.T2 Minimum cost
Although this problem is a proper board , But because I have a habit of doing questions —— Think twice before doing . therefore 5 Minutes later, I have to come up with the conclusion and 5 The conclusion drawn minutes ago is the same as a horse . Success is wasted 5 minute .
however , This is still attributed to my familiarity with the minimum spanning tree , So that I didn't see it at first sight .
3.T3 The guard on the chessboard
This topic , At first glance, it's the kind you can't do , But I still want to it Make it out , So I began to think .
LONG LONG ago( Long long and two dogs )—— It took a lot of time ,There is NO IDEA. But I still did it , With a two-dimensional vis Array to mark , To obtain the 10 Good grades .
To sum up , In the future, we should improve our ability to solve difficult problems , Learn some cheese in advance .
4.T4 Kuglarz
There's nothing to say , Be similar to T3 Well , It's just done .
however , Just a reminder ：
1. open long long.
2. Double the space .
3. Transformation of point and edge weight , And interval DP Tweet of .
Two 、 Code
1. Test code
Paste my small Code ：
T1 A new start
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, INF = 0x3f3f3f3f;
int n, m, MST, cnt, fa[N];
bool vis[N];
struct edge {
int u, v, w;
friend bool operator<(edge A, edge B) {
return A.w < B.w; }
} G[N];
void MakeSet() {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int FindSet(int x) {
if (fa[x] == x)
return x;
return fa[x] = FindSet(fa[x]);
}
void kruskal() {
cnt = MST = 0;
if (n == 1) return ;
MakeSet();
sort(G + 1, G + m + 1);
for (int i = 1; i <= m; i++) {
int x = FindSet(G[i].u), y = FindSet(G[i].v);
if (x == y)
continue;
fa[x] = y;
MST += G[i].w;
cnt++;
if (cnt == n - 1)
return ;
}
}
int main() {
freopen("cost.in", "r", stdin);
freopen("cost.out", "w", stdout);
while(~scanf("%d", &n)) {
if (n == 0) return 0;
m = 0;
for (int i = 1; i < n; i++) {
char s;int k;
cin >> s >> k;
for (int j = 1;j <= k;j++) {
char ss;int kk;
cin >> ss >> kk;
G[++m].u = int(s - 'A' + 1), G[m].v = int(ss - 'A' + 1), G[m].w = kk;
}
}
kruskal();
cout << MST << endl;
}
return 0;
}
2.T2 Minimum cost
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, INF = 0x3f3f3f3f;
int n, m, MST, cnt, fa[N];
bool vis[N];
struct edge {
int u, v, w;
friend bool operator<(edge A, edge B) {
return A.w < B.w; }
} G[N];
void MakeSet() {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int FindSet(int x) {
if (fa[x] == x)
return x;
return fa[x] = FindSet(fa[x]);
}
void kruskal() {
cnt = MST = 0;
if (n == 1) return ;
MakeSet();
sort(G + 1, G + m + 1);
for (int i = 1; i <= m; i++) {
int x = FindSet(G[i].u), y = FindSet(G[i].v);
if (x == y)
continue;
fa[x] = y;
MST += G[i].w;
cnt++;
if (cnt == n - 1)
return ;
}
}
int main() {
freopen("cost.in", "r", stdin);
freopen("cost.out", "w", stdout);
while(~scanf("%d", &n)) {
if (n == 0) return 0;
m = 0;
for (int i = 1; i < n; i++) {
char s;int k;
cin >> s >> k;
for (int j = 1;j <= k;j++) {
char ss;int kk;
cin >> ss >> kk;
G[++m].u = int(s - 'A' + 1), G[m].v = int(ss - 'A' + 1), G[m].w = kk;
}
}
kruskal();
cout << MST << endl;
}
return 0;
}
3.T3 The guard on the chessboard
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, INF = 0x3f3f3f3f;
#define int long long
int n, m, mm, MST, cnt, fa[N];
struct edge {
int u, v, w;
friend bool operator<(edge A, edge B) {
return A.w < B.w; }
} G[N];
void MakeSet() {
for (int i = 1; i <= mm; i++) {
fa[i] = i;
}
}
int FindSet(int x) {
if (fa[x] == x)
return x;
return fa[x] = FindSet(fa[x]);
}
void kruskal() {
bool vis[n + 5][m + 5];
memset(vis, 0, sizeof(vis));
cnt = MST = 0;
if (n == 1)
return ;
MakeSet();
sort(G + 1, G + mm + 1);
for (int i = 1; i <= mm; i++) {
int x = FindSet(G[i].u), y = FindSet(G[i].v);
if (vis[G[i].u][G[i].v])
continue;
fa[x] = y;
MST += G[i].w;
vis[G[i].u][G[i].v] = 1;
cnt++;
if (cnt == n + m)
return ;
}
}
signed main() {
freopen("guard.in", "r", stdin);
freopen("guard.out", "w", stdout);
cin >> n >> m;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
G[++mm].u = i, G[mm].v = j;
scanf("%lld", &G[mm].w);
}
}
kruskal();
cout << MST;
return 0;
}
4.T4 Kuglarz
#include <bits/stdc++.h>
using namespace std;
const int N = 4e6 + 5, INF = 0x3f3f3f3f;
#define int long long
int n, m, MST, cnt, fa[N];
bool vis[N];
struct edge {
int u, v, w;
friend bool operator<(edge A, edge B) {
return A.w < B.w; }
} G[N];
void MakeSet() {
for (int i = 1; i <= m; i++) {
fa[i] = i;
}
}
int FindSet(int x) {
if (fa[x] == x)
return x;
return fa[x] = FindSet(fa[x]);
}
int kruskal() {
cnt = MST = 0;
if (n == 1)
return 0;
MakeSet();
sort(G + 1, G + m + 1);
for (int i = 1; i <= m; i++) {
int x = FindSet(G[i].u), y = FindSet(G[i].v);
if (x == y)
continue;
fa[x] = y;
MST += G[i].w;
cnt++;
if (cnt == n)
return MST;
}
}
signed main() {
freopen("kuglarz.in", "r", stdin);
freopen("kuglarz.out", "w", stdout);
cin >> n;
for (int i = 1;i <= n;i++) {
for (int j = i;j <= n;j++) {
int val;
scanf("%lld", &val);
G[++m].u = i - 1, G[m].v = j, G[m].w = val;
}
}
cout << kruskal();
return 0;
}
2. The positive solution after the exam
T1 A new start
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
#define int long long
int n, m, MST, cnt, v[N], fa[N];
bool vis[N];
struct edge {
int u, v, w;
friend bool operator < (edge A, edge B) {
return A.w < B.w;
}
}G[N];
void MakeSet() {
for (int i = 1;i <= n + 1;i++) {
fa[i] = i;
}
}
int FindSet(int x) {
if (fa[x] == x) return x;
return fa[x] = FindSet(fa[x]);
}
void kruskal() {
cnt = MST = 0;
if (n == 1) return ;
MakeSet();
sort(G + 1, G + m + 1);
for (int i = 1;i <= m;i++) {
int x = FindSet(G[i].u), y = FindSet(G[i].v);
if (x == y) continue;
fa[x] = y;
MST += G[i].w;
cnt++;
if (cnt == n) return ;
}
}
signed main() {
// freopen("start.in", "r", stdin);
// freopen("start.out", "w", stdout);
cin >> n;
for (int i = 1;i <= n;i++) scanf("%lld", &v[i]);
for (int i = 1;i <= n;i++) {
for (int j = 1, val;j <= n;j++) {
scanf("%lld", &val);
G[++m].u = i, G[m].v = j, G[m].w = val;
}
}
for (int i = 1;i <= n;i++) {
G[++m].u = n + 1, G[m].v = i, G[m].w = v[i];
}
kruskal();
cout << MST;
return 0;
}
2.T2 Minimum cost
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, INF = 0x3f3f3f3f;
int n, m, MST, cnt, fa[N];
bool vis[N];
struct edge {
int u, v, w;
friend bool operator<(edge A, edge B) {
return A.w < B.w; }
} G[N];
void MakeSet() {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int FindSet(int x) {
if (fa[x] == x)
return x;
return fa[x] = FindSet(fa[x]);
}
void kruskal() {
cnt = MST = 0;
if (n == 1) return ;
MakeSet();
sort(G + 1, G + m + 1);
for (int i = 1; i <= m; i++) {
int x = FindSet(G[i].u), y = FindSet(G[i].v);
if (x == y)
continue;
fa[x] = y;
MST += G[i].w;
cnt++;
if (cnt == n - 1)
return ;
}
}
int main() {
freopen("cost.in", "r", stdin);
freopen("cost.out", "w", stdout);
while(~scanf("%d", &n)) {
if (n == 0) return 0;
m = 0;
for (int i = 1; i < n; i++) {
char s;int k;
cin >> s >> k;
for (int j = 1;j <= k;j++) {
char ss;int kk;
cin >> ss >> kk;
G[++m].u = int(s - 'A' + 1), G[m].v = int(ss - 'A' + 1), G[m].w = kk;
}
}
kruskal();
cout << MST << endl;
}
return 0;
}
3.T3 The guard on the chessboard
#include <bits/stdc++.h>
using namespace std;
int n, m, x, cnt, nm , f[200005], vis[200005];
long long ans;
struct Node {
int u, v, k;
} e[200005];
bool cmp(Node n, Node m) {
return n.k < m.k; }
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]); }
int main() {
freopen("guard.in", "r", stdin);
freopen("guard.out", "w", stdout);
scanf("%d%d", &n, &m);nm = n * m;
for (int i = 1; i <= n + m; i++) f[i] = i, vis[i] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &x), e[++cnt] = Node{
i, j + n, x};
sort(e + 1, e + 1 + cnt, cmp);
for (int i = 1; i <= nm; i++) {
int fx = find(f[e[i].u]), fy = find(f[e[i].v]);
if (vis[fx] && vis[fy]) continue;
if (fy != fx) vis[fx] |= vis[fy], f[fy] = fx;
else vis[fx] = 1;
ans += e[i].k;
}
printf("%lld", ans);
return 0;
}
4.T4 Kuglarz
#include <bits/stdc++.h>
using namespace std;
const int N = 4e6 + 5, INF = 0x3f3f3f3f;
#define int long long
int n, m, MST, cnt, fa[N];
bool vis[N];
struct edge {
int u, v, w;
friend bool operator<(edge A, edge B) {
return A.w < B.w; }
} G[N];
void MakeSet() {
for (int i = 1; i <= m; i++) {
fa[i] = i;
}
}
int FindSet(int x) {
if (fa[x] == x)
return x;
return fa[x] = FindSet(fa[x]);
}
int kruskal() {
cnt = MST = 0;
if (n == 1)
return 0;
MakeSet();
sort(G + 1, G + m + 1);
for (int i = 1; i <= m; i++) {
int x = FindSet(G[i].u), y = FindSet(G[i].v);
if (x == y)
continue;
fa[x] = y;
MST += G[i].w;
cnt++;
if (cnt == n)
return MST;
}
}
signed main() {
freopen("kuglarz.in", "r", stdin);
freopen("kuglarz.out", "w", stdout);
cin >> n;
for (int i = 1;i <= n;i++) {
for (int j = i;j <= n;j++) {
int val;
scanf("%lld", &val);
G[++m].u = i - 1, G[m].v = j, G[m].w = val;
}
}
cout << kruskal();
return 0;
}
LAST Last , Perfect flowers
边栏推荐
- include 与 require include_once 与 require_once 的区别
- Analysis of the internal principle of LinkedList
- 对象到对象映射-AutoMapper
- [summary of leetcode weekly competition] the 83rd fortnight competition of leetcode (7.23)
- PHP connection MySQL native code
- Window source code analysis (IV): window deletion mechanism
- (iros 2022) monocular visual inertial odometer based on event camera
- Have you ever seen this kind of dynamic programming -- the stock problem of state machine dynamic programming (Part 2)
- Seektiger eco pass STI new progress, log in to ZB on April 14
- 一文读懂Plato Farm的ePLATO，以及其高溢价缘由
猜你喜欢
Pycharm uses CONDA to call the remote server
Plato farm - a farm meta universe game with Plato as the goal
C＃ 倒计时工具
Detailed explanation of various types of files in MySQL
刚获融资的Espresso Systems，知识产权与团队道德双双陷入困境
极致通缩和永动机模型，将推动 PlatoFarm 爆发
初学C＃必须要掌握的基础例题
软件测试与质量学习笔记1---黑盒测试
Pulse style ｜ exclusive interview with Committee -- Tencent engineer Zhang Dawei calls you to eat "crab"
This wechat plug-in is very easy to use
随机推荐
极致通缩和永动机模型，将推动 PlatoFarm 爆发
This wechat plug-in is very easy to use
Translation recommendation | debugging bookkeeper protocol - unbounded ledger
go语言切片Slice和数组Array对比panic runtime error index out of range问题解决
How to learn so many conceptual things in database? Seeking method
Net 3 lines of code to realize the function of text to speech
Window source code analysis (III): window update mechanism
Source code analysis of view event distribution mechanism
数据库高级学习笔记--存储函数
Can multithreading optimize program performance?
Window source code analysis (IV): window deletion mechanism
多线程一定能优化程序性能吗？
pycharm使用conda调用远程服务器
Espresso systems, which has just obtained financing, has both intellectual property rights and team ethics in trouble
Common tool functions are constantly updated
3分钟带你了解微信小程序开发
Several innovative economic models of platofarm have inspired the current metacosmic market
数据不会说谎，Plato Farm就是元宇宙龙头
今天和大家聊一聊mysql数据库的数据类型
Pycharm uses CONDA to call the remote server