搞这种题，没啥好方法和好套路，纯凭数感。凭感觉。
建议先去找一些初等数论的书来搞一搞，练一下数感才行。
比如陈景润，潘承洞写的初等数论。
然后就是一些不等式之类的，也可以。

思路:
设有3个数 a,b,c (a<=b<=c)
那么合并的方式有 C(2,3)C(2,2) = 3种
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)

显然(1) 式最大，即从小到大顺序合并

4个数以上时，可以当成3个数的来处理，因为每次都进行堆排序了
取前两个最小的相乘，后面得的值就越大。

因为每次有+1,让这个1与更大的数相乘就能更大。

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)
这里取决于 ab 和 c,d 谁更大。
acbd          值为((a*c+1)*b+1)*d+1 = a*b*c*d+b*d+d+1  (4)
(4) 显然没有(1)大。
下面太多，就不分析了，和上面类似。
acdb
(ac)(db)(ac)
adbc
adcb
(ad)(cb)(ad)
bcad
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;
}

一：简介

二:划分象限

如上图，将平面坐标系，划分为8个象限
1象限中 dx = 1,dy = k,2象限 dx = 1/k,dy = 1

三:增量表格

规律 当|dx| > |dy| 时 dx=1,dy=k,否则 dx=1/k ,dy = 1

于是 总步长 EPS 应该取 dx,dy 中较大的那一个

具体代码:
https://gitee.com/feng_guang_zhi/games101/tree/develop/Rasterizer

代码如下:

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

先处理(4,70)
可选的位置有 1,2,3,4 这里当然是优先选最大的，即 4, 那么4被占用了。
下一次，若还有4为截止的，那么就只能罚款了。
处理(2,60) 可选位置 1,2 那么选 2
处理(4,50) 可选位置 1,3 ,因为 2,4被占用了,那么选3
处理(3,50) 可选位置 1
处理(1,30) 没有可选位置，那么罚款30
处理(4,20) 没有可选位置 罚款 20
处理(6,10) 可选位置 5,6 那么选6

所以罚款为 30 + 20 = 50

余额为 10000 - 50 = 9950

代码如下:

#include<algorithm>
#include<iostream>

using namespace std;

const int MAXN = 505;

struct Node{
    int deadLine;
    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++){
        cin >> games[i].deadLine;
    }
    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]);

打个log试试如下

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

因为每次都是 add(1)

而query(n) ,表示 1 - n 的前缀和的总和

所以 query(n) 一定是 i

#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;
}

void add(int id,int delta){
    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++){
        add(ranks[i],1);
        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;
}

可以发现规律，每次起始于，入度为0的点，结束于出度为0的点

比如 10 有 3个分叉，那么可以贡献3个路径数，

dp[i] 表是，到当前点的路径数，
即10向前有3条边，那么根据加法原理，那么6,7,9 直接加上dp[10] 的值即可

注意点:
因为孤立点，不能算答案。

所以起始点，要加上这个条件 : outDegree[i] > 0

由图可知，一共9个叶子节点，即是答案。

1 . 朴素 dfs
这个会TLE ,加上记忆化搜索就行

#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 表示 根节点到 当前点的异或总和

异或和求和其实是类似。
慢足交换律，结合律

且 a^b^b = a

对任意 x 有 x^x = 0 , x^0 = x

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

异或比树上区间求和稍微简单一些，因为抵消掉的，不用去求LCA
如果是树上区间求和，那么需要去求出，LCA的值，然后再根据容斥原理，进行计算

#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;
}

只要该地块处于同一个连通块内，那么必然可以相互到达。
那么查询的结果，就是该地块 (x,y) 所在的连通块的大小。

所以使用一个blockNum 来表是连通块的大小

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 算法的目的:
即dist[to] 表示，到达该点，所经过的边权要最小，即和该点，相邻的边的权值的最小值。

而dijsktra 算法的 dist[to] 是表示，到达该点的边权总和的最小值。

注意点:
优先队列 priority_queue 的 cmp 和 sort 的 cmp 是反过来的

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

最终答案 2 + 3 + 4 + 5 = 14

第一步，找到 到2的最短边 2,到5的最短边10
第二步，找到 到3的最短边3，到5的最短边7
第三步: 找到 到4的最短边4，到5的最短边6
第四步: 找到 到5的最短边5
第五步：没有可松弛的边，结束。

看以发现规律，每一次都是连的最短的边，本质和kruskal 算法一样的，从最小的边开始连。

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
参考文章: https://www.acwing.com/solution/content/189000/

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

样例:
2 2
1 1 2 1

走一遍 kruskal 算法，把边按边权排序即可。

代码如下:

#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 算法

堆优化感觉，更适合邻接表，因为在邻接矩阵里，还是得遍历n次，即每个顶点，
然后堆优化的优势就没有完全发挥出来来。

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

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

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

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

相同点：都是先从最小的dist[i] 开始，然后bfs,去松弛边

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

贪心的思想就是，尽量使经过的边要最小。
表现在prim算法里，就是，每次都是去找边权最小的那条边

表现在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;
}