1.4万

wuno
bestkain
1_68
yutiti80

fxh01
Richard_H

Warsaw
JKgame

x.t.
cubane
Grin._4

dushucheng0901
StkOvflow
kerry2023

4个数，就是C(2,4)
C(2,3)C(2,2) = 6 * 3 = 18 种
n个数,就是 C(2,n)
C(2,n-1)C(2,2) 种

3个数的合并顺序

abc
acb
bca

(a*b+1)*c+1 = a*b*c+c+1 (1)
(a*c+1)*b+1 = a*b*c+b+1 (2)
(b*c+1)*a+1 = a*b*c+a+1  (3)


4个数以上时，可以当成3个数的来处理，因为每次都进行堆排序了

4个数时，设a,b,c,d(a<=b<=c<=d),有18种合并方式

abcd          值为((a*b+1)*c+1)*d+1 = a*b*c*d+d*c+d+1 (1)
abdc          值为((a*b+1)*d+1)*c+1 = a*b*c*d+d*c+c+1  (2)
(ab)(dc)(ab)  值为(a*b+1)*(d*c+1)+1 = a*b*c*d+d*c+a*b+2 (3)

acbd          值为((a*c+1)*b+1)*d+1 = a*b*c*d+b*d+d+1  (4)
(4) 显然没有(1)大。

acdb
(ac)(db)(ac)
bcda
(bc)(da)(bc)
bdac
bdca
(bd)(ca)(bd)
cdab
cdba
(cd)(ba)(cd)


#include<iostream>
#include<queue>
#include<vector>

using namespace std;

using i64 = long long;

int n;

int main(){
cin >> n;
priority_queue<i64,vector<i64>,less<i64>> maxHeap;
priority_queue<i64,vector<i64>,greater<i64>> minHeap;
for(int i = 1;i <= n;i++){
i64 a;
cin >> a;
maxHeap.push(a);
minHeap.push(a);
}

i64 maxS = -1;
while(maxHeap.size() > 1){
i64 a = maxHeap.top();
maxHeap.pop();
i64 b = maxHeap.top();
maxHeap.pop();
i64 c = a * b + 1;
maxHeap.push(c);
}
maxS = maxHeap.top();

i64 minS = -1;
while(minHeap.size() > 1){
i64 a = minHeap.top();
minHeap.pop();
i64 b = minHeap.top();
minHeap.pop();
i64 c = a * b + 1;
minHeap.push(c);
}
minS = minHeap.top();

auto ans = minS - maxS;
cout << ans << endl;
return 0;
}


1象限中 dx = 1,dy = k,2象限 dx = 1/k,dy = 1

void Rasterizer::DDALine(Eigen::Vector3f start,Eigen::Vector3f end){
int dx = round(end.x() - start.x());
int dy = round(end.y() - start.y());
int eps = std::max(abs(dx),abs(dy));
float stepX = (float)dx / eps;
float stepY = (float)dy / eps;
Eigen::Vector3f color(1.0f,0.0f,0.0f);
Eigen::Vector3f sx(start.x(),start.y(),start.z());
for(int i = 1;i <= eps;i++){
setPixel(sx,color);
sx += Eigen::Vector3f(stepX,stepY,0.0f);
}
}

rasterizer.DDALine(Eigen::Vector3f(200,200,0),Eigen::Vector3f(500,456,0));


10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

4 2 4 3 1 4 6
70 60 50 40 30 20 10

#include<algorithm>
#include<iostream>

using namespace std;

const int MAXN = 505;

struct Node{
int punity;
bool operator < (const Node& ohter) const{
return punity > ohter.punity;
}
};

Node games[MAXN];
bool used[MAXN];

int money;
int n;

int main(){
cin >> money;
cin >> n;
for(int i = 1;i <= n;i++){
}
for(int i = 1;i <= n;i++){
cin >> games[i].punity;
}

sort(games + 1,games + n + 1);

int punityMoney = 0;

for(int i = 1; i <= n;i++){
bool needPunity = true;
for(int j = games[i].deadLine;j >= 1;j--){
if(!used[j]){
used[j] = true;
needPunity = false;
break;
}
}
if(needPunity){
punityMoney += games[i].punity;
}
}
int ans = money - punityMoney;
cout << ans << endl;
return 0;
}


res += query(n) - query(ranks[i]);

---->1
---->2
---->3
---->4
---->5
6
---->1
---->2
---->3
0

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

using i64 = long long;

const int MAXN = 5e5 + 10;

i64 bitree[MAXN];
int ranks[MAXN];

struct Node{
int val;
int idx;
bool operator < (const Node& other) const{
return val < other.val;
}
};
Node arr[MAXN];

int n;

i64 lowbit(int x){
return x & -x;
}

for(int i = id;i <= n;i += lowbit(i)){
bitree[i] += delta;
}
}

i64 query(int id){
i64 res = 0;
for(int i = id;i >= 1;i -= lowbit(i)){
res += bitree[i];
}
return res;
}

i64 solve(){
memset(bitree,0,sizeof bitree);
for(int i = 1;i <= n;i++){
int a;
cin >> a;
arr[i] = {a,i};
}
sort(arr + 1, arr + 1 + n);
for(int i = 1;i <= n;i++){
ranks[arr[i].idx] = i;
}
i64 res = 0;
for(int i = 1;i <= n;i++){
res += i - query(ranks[i]);
}
return res;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

while(cin >> n){
if(n == 0){
break;
}
auto ans = solve();
cout << ans << '\n';
}

return 0;
}


dp[i] 表是，到当前点的路径数，

1 . 朴素 dfs

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

const int MAXN = 1e5 + 10;
vector<int> graph[MAXN];
int inDegree[MAXN];
int outDegree[MAXN];

int n,m;

int dfs(int cur){
if(outDegree[cur] == 0){
return 1;
}
int res = 0;
for(auto ne : graph[cur]){
res += dfs(ne);
}
return res;
}

int main(){
cin >> n >> m;
for(int i = 1;i <= m;i++){
int a,b;
cin >> a >> b;
graph[a].push_back(b);
inDegree[b]++;
outDegree[a]++;
}
int ans = 0;
for(int i = 1;i <= n;i++){
if(inDegree[i] == 0 && outDegree[i] > 0){
ans += dfs(i);
}
}
cout << ans << endl;
return 0;
}


2 记忆化搜索

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

const int MAXN = 1e5 + 10;
vector<int> graph[MAXN];
int inDegree[MAXN];
int outDegree[MAXN];

int dp[MAXN];

int n,m;

int dfs(int cur){
if(outDegree[cur] == 0){
return 1;
}
if(dp[cur] != -1){
return dp[cur];
}
int res = 0;
for(auto ne : graph[cur]){
res += dfs(ne);
}
dp[cur] = res;
return res;
}

int main(){
cin >> n >> m;
for(int i = 1;i <= m;i++){
int a,b;
cin >> a >> b;
graph[a].push_back(b);
inDegree[b]++;
outDegree[a]++;
}
memset(dp,-1,sizeof dp);
int ans = 0;
for(int i = 1;i <= n;i++){
if(inDegree[i] == 0 && outDegree[i] > 0){
ans += dfs(i);
}
}
cout << ans << endl;
return 0;
}


3 入度bfs 拓扑排序

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

const int MAXN = 1e5 + 10;
vector<int> graph[MAXN];
int inDegree[MAXN];
int outDegree[MAXN];

int dp[MAXN];

int n,m;

void topSort(){
queue<int> q;
for(int i = 1;i <= n;i++){
if(inDegree[i] == 0 && outDegree[i] > 0){
q.push(i);
dp[i] = 1;
}
}
while(!q.empty()){
auto cur = q.front();
q.pop();
for(auto ne : graph[cur]){
inDegree[ne]--;
dp[ne] += dp[cur];
if(inDegree[ne] == 0){
q.push(ne);
}
}
}
}

int main(){
cin >> n >> m;
for(int i = 1;i <= m;i++){
int a,b;
cin >> a >> b;
graph[a].push_back(b);
inDegree[b]++;
outDegree[a]++;
}
topSort();
int ans = 0;
for(int i = 1;i <= n;i++){
if(outDegree[i] == 0){
ans += dp[i];
}
}
cout << ans << endl;
return 0;
}


xors 表示 根节点到 当前点的异或总和

0是幺元，x是自己的逆元。在整数域下，满足阿贝尔群的性质。

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int MAXM = 1e5 + 10;

struct Node{
int to;
int weight;
};

vector<Node> graph[MAXM];

int xors[MAXM];

int m,q;

void dfs(int node,int fa){
for(auto ne : graph[node]){
if(ne.to == fa){
continue;
}
xors[ne.to] = xors[node] ^ ne.weight;
dfs(ne.to,node);
}
}

int main(){
cin >> m;
for(int i = 1;i < m;i++){
int a,b,w;
cin >> a >> b >> w;
graph[a].push_back({b,w});
graph[b].push_back({a,w});
}

dfs(1,-1);
cin >> q;
for(int i = 1;i <= q;i++){
int a,b;
cin >> a >> b;
cout << (xors[a] ^ xors[b]) << endl;
}

return 0;
}


dfs 代码

#include<iostream>

using namespace std;

const int MAXN = 1005;
const int dirs[][2] = {{-1,0},{1,0},{0,1},{0,-1}};

char grid[MAXN][MAXN];

//每个点(x,y)的blockId
int blockIds[MAXN][MAXN];
//block的大小
int blockNum[MAXN * MAXN];
int block;

int n,m;

bool inArea(int x,int y){
return x >= 1 && x <= n && y >= 1 && y <= n;
}

void dfs(int x,int y){
for(auto &d : dirs){
int nx = x + d[0];
int ny = y + d[1];
if(inArea(nx,ny) && !blockIds[nx][ny] &&
grid[x][y] ^ grid[nx][ny]){
blockIds[nx][ny] = block;
blockNum[block]++;
dfs(nx,ny);
}
}
}

int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> grid[i] + 1;
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(!blockIds[i][j]){
block++;
blockIds[i][j] = block;
blockNum[block]++;
dfs(i,j);
}
}
}
int qx,qy;
for(int i = 1;i <= m;i++){
cin >> qx >> qy;
cout << blockNum[blockIds[qx][qy]] << endl;
}
return 0;
}


bfs 代码

#include<iostream>
#include<queue>

using namespace std;

using PII = pair<int,int>;

const int MAXN = 1005;
const int dirs[][2] = {{-1,0},{1,0},{0,1},{0,-1}};

char grid[MAXN][MAXN];

//每个点(x,y)的blockId
int blockIds[MAXN][MAXN];
//block的大小
int blockNum[MAXN * MAXN];
int block;

int n,m;

bool inArea(int x,int y){
return x >= 1 && x <= n && y >= 1 && y <= n;
}

void bfs(int x,int y){
queue<PII> q;
q.push({x,y});
while(!q.empty()){
auto cur = q.front();
q.pop();
for(auto &d : dirs){
int nx = cur.first + d[0];
int ny = cur.second + d[1];
if(inArea(nx,ny) && !blockIds[nx][ny] &&
grid[cur.first][cur.second] ^ grid[nx][ny]){
blockIds[nx][ny] = block;
blockNum[block]++;
q.push({nx,ny});
}
}
}

}

int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> grid[i] + 1;
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(!blockIds[i][j]){
block++;
blockIds[i][j] = block;
blockNum[block]++;
bfs(i,j);
}
}
}
int qx,qy;
for(int i = 1;i <= m;i++){
cin >> qx >> qy;
cout << blockNum[blockIds[qx][qy]] << endl;
}
return 0;
}


prim 算法的目的:

sort 的 cmp < 表示 从小到大排序。

5
0 2 0 0 10
2 0 3 0 7
0 3 0 4 6
0 0 4 0 5
10 7 6 5 0

1 朴素 prim 算法，邻接表

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

struct Node{
int to;
int weight;
};

vector<Node> graph[MAXN];
int dist[MAXN];
bool vis[MAXN];

int n;

int prim(int start){
memset(dist,0x3f,sizeof dist);
dist[start] = 0;
int ans = 0;
for(int i = 1;i <= n;i++){
int minId = -1;
int minDis = INF;
for(int j = 1;j <= n;j++){
if(!vis[j] && dist[j] < minDis){
minDis = dist[j];
minId = j;
}
}
if(minId == -1 || vis[minId]){
continue;
}
vis[minId] = true;
for(auto ne : graph[minId]){
int to = ne.to;
int w = ne.weight;
if(!vis[to] && dist[to] > w){
dist[to] = w;
}
}
}
for(int i = 1;i <= n;i++){
ans += dist[i];
}
return ans;
}

int main(){
cin >> n;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
int w;
cin >> w;
graph[i].push_back({j,w});
graph[j].push_back({i,w});
}
}
auto ans = prim(1);
cout << ans << endl;
return 0;
}


2 朴素 prim 算法，邻接矩阵

#include<iostream>
#include<cstring>

using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int graph[MAXN][MAXN];
int dist[MAXN];
bool vis[MAXN];

int n;

int prim(int start){
memset(dist,0x3f,sizeof dist);
dist[start] = 0;
for(int i = 1;i <= n;i++){
int minId = -1;
int minDis = INF;
for(int j = 1;j <= n;j++){
if(!vis[j] && dist[j] < minDis){
minDis = dist[j];
minId = j;
}
}
if(minId == -1 || vis[minId]){
continue;
}
vis[minId] = true;
for(int j = 1;j <= n;j++){
if(!vis[j] && dist[j] > graph[minId][j]){
dist[j] = graph[minId][j];
}
}
}
int ans = 0;
for(int i = 1;i <= n;i++){
ans += dist[i];
}
return ans;
}

int main(){
cin >> n;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
cin >> graph[i][j];
}
}

auto ans = prim(1);
cout << ans << endl;

return 0;
}


3 堆优化 prim 算法 邻接表

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

struct Node{
int to;
int weight;
bool operator < (const Node& other)const{
return weight > other.weight;
}
};

vector<Node> graph[MAXN];
int dist[MAXN];
bool vis[MAXN];

int n;

int prim(int start){
memset(dist,0x3f,sizeof dist);
priority_queue<Node> q;
dist[start] = 0;
q.push({start,0});
while(!q.empty()){
auto cur = q.top();
q.pop();
vis[cur.to] = true;
for(auto ne : graph[cur.to]){
int to = ne.to;
int w = ne.weight;
if(!vis[to] && dist[to] > w){
dist[to] = w;
q.push({to,w});
}
}
}
int ans = 0;
for(int i = 1;i <= n;i++){
ans += dist[i];
}
return ans;
}

int main(){
cin >> n;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
int w;
cin >> w;
graph[i].push_back({j,w});
graph[j].push_back({i,w});
}
}
auto ans = prim(1);
cout << ans << endl;
return 0;
}


4 prim算法，堆优化 ，邻接矩阵

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

struct Node{
int to;
int weight;
bool operator < (const Node& other) const{
return weight > other.weight;
}
};

int graph[MAXN][MAXN];
int dist[MAXN];
bool vis[MAXN];

int n;

int prim(int start){
priority_queue<Node> q;
memset(dist,0x3f,sizeof dist);
dist[start] = 0;
q.push({start,0});
while (!q.empty()){
auto cur = q.top();
q.pop();
vis[cur.to] = true;
for(int i = 1;i <= n;i++){
if(!vis[i] && dist[i] > graph[cur.to][i]){
dist[i] = graph[cur.to][i];
q.push({i,dist[i]});
}
}
}
int ans = 0;
for(int i = 1;i <= n;i++){
ans += dist[i];
}
return ans;

}

int main(){
cin >> n;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
cin >> graph[i][j];
}
}

auto ans = prim(1);
cout << ans << endl;

return 0;
}


5 Kruskal 算法

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int MAXN = 105;

struct Edge{
int from,to;
int weight;
bool operator < (const Edge& other)const{
return weight < other.weight;
}
};

vector<Edge> edges;

int fa[MAXN];

int n;

void init(){
for(int i = 1;i <= n;i++){
fa[i] = i;
}
}

int find(int x){
if(x == fa[x]){
return x;
}
return fa[x] = find(fa[x]);
}

int main(){
cin >> n;
init();
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
int w;
cin >> w;
if(w != 0){
edges.push_back({i,j,w});
}
}
}
sort(edges.begin(),edges.end());

int ans = 0;
for(auto& edge : edges){
int f = edge.from;
int t = edge.to;
int w = edge.weight;
int pf = find(f);
int pt = find(t);
if(pf != pt){
fa[pf] = pt;
ans += w;
}
}

cout << ans << endl;

return 0;
}


1347：【例4-8】格子游戏 http://ybt.ssoier.cn:8088/problem_show.php?pid=1347

1.先建立网格边,如下图:

2 2
1 1 2 1

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int MAXN = 1005;
const int MAXM = MAXN * MAXN;

struct Edge{
int from,to;
int weight;
bool operator < (const Edge& other)const{
return weight < other.weight;
}
};

vector<Edge> edges;

int fa[MAXM];

int row,col;

bool inArea(int x,int y){
return x >= 1 && x <= row && y >= 1 && y <= col;
}

void init(){
for(int i = 1;i < MAXM;i++){
fa[i] = i;
}
}

int find(int x){
if(x == fa[x]){
return x;
}
return fa[x] = find(fa[x]);
}

int main(){
cin >> row >> col;

init();

for(int i = 1;i <= row;i++){
for(int j = 1;j <= col;j++){
int rx = i;
int ry = j + 1;
if(inArea(rx,ry)){
int p = (i - 1) * col + j;
int pr = (rx - 1) * col + ry;
edges.push_back({p,pr,2});
}
int dx = i + 1;
int dy = j;
if(inArea(dx,dy)){
int p = (i - 1) * col + j;
int pr = (dx - 1) * col + dy;
edges.push_back({p,pr,1});
}
}
}
int x1,y1,x2,y2;
while(cin >> x1 >> y1 >> x2 >> y2){
int id1 = (x1 - 1) * col + y1;
int id2 = (x2 - 1) * col + y2;
int pid1 = find(id1);
int pid2 = find(id2);
if(pid1 != pid2){
fa[pid1] = pid2;
}
}

sort(edges.begin(),edges.end());

int ans = 0;
for(auto edge : edges){
int f = edge.from;
int t = edge.to;
int w = edge.weight;
int pf = find(f);
int pt = find(t);
if(pf != pt){
fa[pf] = pt;
ans += w;
}
}

cout << ans << endl;

return 0;
}


1 朴素prim 算法，邻接表
2 朴素prim 算法，邻接矩阵
3 堆优化prim 算法,邻接表
4 堆优化prim 算法，邻接矩阵
5 Kruskal 算法

prim 算法 前置知识，贪心、dp,dijsktra算法

prim算法和dijsktra算法的区别就是

dijsktra算法 的松弛是 dist[to] = dist[from] + graph[from][to]

prim算法 的松弛是 dist[to] = graph[from][to]

kruskal 算法，前置知识，并查集，贪心算法。

1 朴素 Prim 算法 邻接表

#include<iostream>
#include<vector>
#include<cstring>
#include<set>

using namespace std;

using PII = pair<int,int>;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

struct Node{
int from,to;
int dis;
};

vector<Node> graph[MAXN];
set<PII> paths;
bool vis[MAXN];
int dist[MAXN];
int froms[MAXN];

int n,m;

bool prim(int start){
memset(dist,0x3f,sizeof dist);
dist[start] = 0;
for(int i = 1;i <= n;i++){
int minId = -1;
int minDis = INF;
for(int j = 1;j <= n;j++){
if(!vis[j] && dist[j] < minDis){
minDis = dist[j];
minId = j;
}
}
vis[minId] = true;
if(froms[minId]){
int f = min(froms[minId],minId);
int t = max(froms[minId],minId);
paths.insert({f,t});
}
for(auto node : graph[minId]){
int to = node.to;
int d = node.dis;
if(!vis[to] && dist[to] > d){
dist[to] = d;
froms[to] = minId;
}
}
}
return true;
}

int main(){
cin >> n >> m;
for(int i = 1;i <= m;i++){
int from,to,d;
cin >> from >> to >> d;
graph[from].push_back({from,to,d});
graph[to].push_back({to,from,d});
}
prim(1);
for(auto pii : paths){
cout << pii.first <<' ' << pii.second << '\n';
}
return 0;
}


2 朴素 prim 算法，邻接矩阵

#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>

using namespace std;
using PII = pair<int,int>;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int graph[MAXN][MAXN];
int dist[MAXN];
int froms[MAXN];
bool vis[MAXN];

set<PII> paths;

int n,m;

void prim(int start){
memset(dist,0x3f,sizeof dist);
dist[start] = 0;
for(int i = 1;i <= n;i++){
int minId = -1;
int minDis = INF;
for(int j = 1;j <= n;j++){
if(!vis[j] && dist[j] < minDis){
minDis = dist[j];
minId = j;
}
}
vis[minId] = true;
if(froms[minId]){
int f = min(froms[minId],minId);
int t = max(froms[minId],minId);
paths.insert({f,t});
}
for(int j = 1;j <= n;j++){
if(!vis[j] && dist[j] > graph[minId][j]){
dist[j] = graph[minId][j];
froms[j] = minId;
}
}
}
}

int main(){
memset(graph,0x3f,sizeof graph);

cin >> n >> m;

for(int i = 1;i <= m;i++){
int from,to,dis;
cin >> from >> to >> dis;
graph[from][to] = dis;
graph[to][from] = dis;
}

prim(1);
for(auto p : paths){
cout << p.first <<' ' << p.second << '\n';
}

return 0;
}


3 堆优化 prim 算法 ，邻接表

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<cstring>

using namespace std;
using PII = pair<int,int>;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

struct Node{
int to;
int weight;
bool operator < (const Node& other)const{
return weight > other.weight;
}
};

vector<Node> graph[MAXN];
int dist[MAXN];
bool vis[MAXN];
int froms[MAXN];
priority_queue<Node> q;
set<PII> paths;

int n,m;

void prim(int start){
memset(dist,0x3f,sizeof dist);
dist[start] = 0;
q.push({start,0});
int visCnt = 0;
while(!q.empty()){
auto cur = q.top();
q.pop();
if(vis[cur.to]){
continue;
}
vis[cur.to] = true;
if(froms[cur.to]){
int f = min(froms[cur.to],cur.to);
int t = max(froms[cur.to],cur.to);
paths.insert({f,t});
}
if(++visCnt == n){
break;
}
for(auto ne : graph[cur.to]){
int to = ne.to;
int w = ne.weight;
if(!vis[to] && w < dist[to]){
dist[to] = w;
froms[to] = cur.to;
q.push(ne);
}
}
}
}

int main(){
cin >> n >> m;
for(int i = 1;i <= m;i++){
int from,to,weight;
cin >> from >> to >> weight;
graph[from].push_back({to,weight});
graph[to].push_back({from,weight});
}

prim(1);

for(auto p : paths){
cout << p.first << ' ' << p.second << endl;
}

return 0;
}


4 堆优化 prim 算法，邻接矩阵

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<set>

using namespace std;

using PII = pair<int,int>;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int graph[MAXN][MAXN];
int dist[MAXN];
bool vis[MAXN];
int froms[MAXN];

struct Node{
int to;
int weight;
bool operator < (const Node& other)const{
return weight > other.weight;
}
};

priority_queue<Node> q;
set<PII> paths;

int n,m;

void prim(int start){
memset(dist,0x3f,sizeof dist);
dist[start] = 0;
q.push({start,0});
while(!q.empty()){
auto cur = q.top();
q.pop();
if(vis[cur.to]){
continue;
}
vis[cur.to] = true;
if(froms[cur.to]){
int f = min(cur.to,froms[cur.to]);
int t = max(cur.to,froms[cur.to]);
paths.insert({f,t});
}
for(int j = 1;j <= n;j++){
if(!vis[j] && graph[cur.to][j] < dist[j]){
dist[j] = graph[cur.to][j];
froms[j] = cur.to;
q.push({j,dist[j]});
}
}
}
}

int main(){
cin >> n >> m;

memset(graph,0x3f,sizeof graph);

for(int i = 1;i <= m;i++){
int from,to,weight;
cin >> from >> to >> weight;
graph[from][to] = weight;
graph[to][from] = weight;
}

prim(1);

for(auto p : paths){
cout << p.first << ' ' << p.second << endl;
}

return 0;
}


5 Kruskal 算法

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

using PII = pair<int,int>;

const int MAXN = 105;
const int MAXM = MAXN * MAXN;

struct Edge{
int from,to;
int weight;
};

Edge edges[MAXM];

vector<Edge> paths;

int fa[MAXN];

int n,m;

void init(){
for(int i = 1;i <= n;i++){
fa[i] = i;
}
}

int find(int x){
if(x == fa[x]){
return x;
}
return fa[x] = find(fa[x]);
}

bool cmpEdge(const Edge& a,const Edge& b){
return a.weight < b.weight;
}

bool cmpSet(const Edge& a,const Edge& b){
if(a.from == b.from){
return a.to < b.to;
}
return a.from < b.from;
}

int main(){
cin >> n >> m;

init();

for(int i = 1;i <= m;i++){
int from,to,weight;
cin >> from >> to >> weight;
if(from > to){
swap(from,to);
}
edges[i] = {from,to,weight};
}

sort(edges + 1,edges + m + 1,cmpEdge);

for(int i = 1;i <= m;i++){
int a = edges[i].from;
int b = edges[i].to;
int pa = find(a);
int pb = find(b);
if(pa != pb){
fa[pa] = pb;
paths.push_back(edges[i]);
}
}

sort(paths.begin(),paths.end(),cmpSet);

for(auto p : paths){
cout << p.from << ' ' << p.to << endl;
}

return 0;
}