POJ 2421 Constructing Roads

题目链接：
[kuangbin带你飞]专题六 最小生成树 D - Constructing Roads

输入矩阵，求最小生成树。其中有的边已经联通，不需要再计算，将其权值置为0即可。

//#include"stdafx.h"
#include <iostream>
#include <cstdio>
#include <cmath>
#include<cstring>
#include <algorithm>
using namespace std;

struct edge
{
    int s, e, w;
};

edge e[10008];
int p[108];
int n, ans = 0, cnt = 0;
int map[108][108];

bool cmp(edge a, edge b) { return a.w < b.w; }
int find(int x){ return x == p[x] ? x : p[x] = find(p[x]); }

void kruscal()
{
    sort(e, e + cnt, cmp);

    for (int i = 0; i < cnt; i++)
    {
        int x = find(e[i].s);
        int y = find(e[i].e);
        if (x != y)
        {
            p[x] = y;
            ans += e[i].w;
        }
    }
    cout << ans << endl;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> map[i][j];

    int m, x, y;
    for (int i = 0; i <= n; i++) p[i] = i;

    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        //ans += map[x - 1][y - 1];
        map[x - 1][y - 1] = 0;
    }



    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            {
                e[cnt].s = i;
                e[cnt].e = j;
                e[cnt++].w = map[i][j];
            }

    kruscal();

    return 0;

}