This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.
@[TOC](Table of Contents) Problem Set Master Index Study reference blogs: Solving Minimum Spanning Tree Problems (Kruskal Algorithm & Prim Algorithm), Data Structure Study Notes <8> Sorting
08-Graph 7 Highway Connecting All Villages (30 pts)
A very straightforward minimum spanning tree problem, but the code is somewhat lengthy. Optional — write it if you have time.
Problem Summary
Given the highway construction costs between all villages, calculate the minimum cost to connect all villages. A classic minimum spanning tree template problem, solvable with Kruskal’s algorithm.
Code
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxm = 3030;
const int maxn = 1005;
const int inf = 0x3f3f3f3f;
int fa[maxn];
int N,M;//顶点数 边数
struct edge {
int u,v,w;
bool operator<(const edge& a) const {
return w < a.w;
}
} E[maxm];//最大边数maxm
int find(int x) {
return fa[x] == -1 ? x : fa[x] = find(fa[x]);
}
int Kruskal() {
for(int i = 0; i <= N; ++i) fa[i] = -1;
int ans,cnt;
ans = cnt = 0;
sort(E,E+M);
for(int i = 0; i < M; ++i) {
int x = find(E[i].u);
int y = find(E[i].v);
if(x != y) {
fa[x] = y;
ans += E[i].w;
cnt++;
}
if(cnt == N-1) break;
}
if(cnt != N-1) return -1;
else return ans;
}
int main(){
cin >> N >> M;
for(int i = 0; i < M; ++i) {
cin >> E[i].u >> E[i].v >> E[i].w;
}
cout << Kruskal() << endl;
return 0;
}Test Cases
Test cases are as follows:
08-Graph 8 How Long Does It Take (25 pts)
A variation of topological sort. The program is not too complex, so it’s recommended to give it a try.
Problem Summary
Given a project with N activity checkpoints (numbered 0 to N-1) and M activities, where each of the M lines contains three integers representing the start checkpoint number, end checkpoint number, and duration, find the earliest completion time of the project.
Approach
Compute the earliest completion time for each checkpoint during topological sorting. The earliest completion time for the entire project is the maximum among all checkpoint earliest completion times.
Code
// 08-图8 How Long Does It Take (25分)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 105;
const int inf = 0x3f3f3f;
int N,M,ans;
int edge[maxn][maxn];//所有活动
int mint[maxn];//到每个活动检查点的最短时间
int In[maxn];//每个活动检查点的入度
void init() {
memset(edge, -1, sizeof(edge));
memset(mint, 0, sizeof(mint));
memset(In, 0, sizeof(In));
ans = 0;
}
bool Topsort() {//拓扑排序
queue<int> q;
for(int i = 0; i < N; ++i) {
if(In[i] == 0) {
mint[i] = 0;//若为起点，则最短时间当然为0
q.push(i);
}
}
int cnt = 0;
while(!q.empty()) {
int v = q.front();
q.pop();
cnt++;
for(int i = 0; i < N; ++i) {
if(v == i || edge[v][i] == -1) continue;//检查以v为起点的所有边
In[i]--;
if(mint[i] < mint[v] + edge[v][i])
mint[i] = mint[v] + edge[v][i];
if(In[i] == 0) q.push(i);
}
}
if(cnt != N) return false;
else return true;
}
int main(){
ios::sync_with_stdio(false);
cin >> N >> M;
init();
for(int i = 0; i < M; ++i) {
int u,v,w;
cin >> u >> v >> w;
edge[u][v] = w;
In[v]++;
}
if(Topsort()) {
for(int i = 0; i < N; ++i) {
if(mint[i] > ans) ans = mint[i];
}
cout << ans << endl;
} else cout << "Impossible" << endl;
return 0;
}Test Cases
08-Graph 9 Critical Activities (30 pts)
After listening to the lecture, the approach for this problem should be fairly clear. You just need to add some content on top of the previous problem’s program. However, the code is still somewhat lengthy, so proceed based on your available time. Enter with caution.
Problem Summary
Similar to the previous problem, but in addition to the earliest completion time, the latest completion time is also required to derive the slack time. Finally, output whether the task can be completed, and if so, output the critical activities (activities with no slack time).
Code
// 08-图8 How Long Does It Take (25分)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 105;
const int inf = 0x3f3f3f;
int N,M,ans,last;
int edge[maxn][maxn];//所有活动
int mint[maxn];//到每个活动检查点的最短时间
int maxt[maxn];//到每个活动检查点的最长时间
int In[maxn];//每个活动检查点的入度
int Out[maxn];//每个活动检查点的出度
void init() {
memset(edge, -1, sizeof(edge));
memset(mint, 0, sizeof(mint));
memset(maxt, 0x3f, sizeof(maxt));
memset(In, 0, sizeof(In));
memset(Out, 0, sizeof(Out));
ans = last = 0;
}
bool Get_Mint() {
queue<int> q;
for(int i = 1; i <= N; ++i) {
if(In[i] == 0)
q.push(i);
}
int cnt = 0;
while(!q.empty()) {
int v = q.front();
q.pop();
cnt++;
for(int i = 1; i <= N; ++i) {
if(edge[v][i] == -1) continue;
In[i]--;
//<v,i>有有向边
mint[i] = max(mint[i], mint[v] + edge[v][i]);
if(In[i] == 0)
q.push(i);
}
}
if(cnt != N) return false;
else return true;
}
void Get_Maxt() {
queue<int> q;
maxt[last] = ans;
for(int v = 1; v <= N; ++v) {
if(Out[v] == 0) {
q.push(v);
Out[v] = -1;
}
}
while(!q.empty()) {
int v = q.front();
q.pop();
for(int i = 1; i <= N; ++i) {
if(edge[i][v] == -1) continue;
Out[i]--;
//<i,v>有有向边
maxt[i] = min(maxt[i], maxt[v] - edge[i][v]);
if(Out[i] == 0) {
q.push(i);
Out[i] = -1;
}
}
}
}
int main(){
cin >> N >> M;
init();
for(int i = 1; i <= M; ++i) {
int u,v,w;
cin >> u >> v >> w;
edge[u][v] = w;
In[v]++;
Out[u]++;
}
if(Get_Mint()) {
for(int i = 1; i <= N; ++i) {
if(ans < mint[i]) {
ans = mint[i];
last = i;
}
}
cout << ans << endl;
Get_Maxt();
for(int i = 1; i <= N; ++i) {
for(int j = N; j >= 1; --j) {
if(edge[i][j] != -1 && edge[i][j] == maxt[j] - mint[i]) {
cout << i << "->" << j << endl;
}
}
}
} else cout << 0 << endl;
return 0;
}Test Cases
Kept getting WA on test cases 2 and 5… finally found out two lines of code were swapped qwq
喜欢的话，留下你的评论吧～