Quiz/17472_MST.cpp at main · sangjun12458/Quiz · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <vector>
#include <queue>
#define P pair<int, int>

using namespace std;

int n, m;
int map[100][100];
P link[100][100];
vector<pair<P, P>> v;
priority_queue<pair<int, pair<P, P>>> pq;

P do_find(P node)
{
    if (link[node.first][node.second] == node)
        return node;
    return link[node.first][node.second] = do_find(link[node.first][node.second]);
}
void do_union(P n1, P n2)
{
    P r1 = do_find(n1);
    P r2 = do_find(n2);
    if (r1.first <= r2.first && r1.second <= r2.second)
        link[r2.first][r2.second] = r1;
    else
        link[r1.first][r1.second] = r2;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
            link[i][j] = make_pair(i, j);
        }
    }

    for (int i = 0; i < n; i++)
    {
        vector<P> temp;
        for (int j = 0; j < m; j++)
        {
            if (map[i][j] == 0)
                continue;
            temp.push_back(link[i][j]);
        }
        for (int j = 1; j < temp.size(); j++)
        {
            P p1 = temp[j - 1];
            P p2 = temp[j];
            int dist = p2.second - p1.second - 1;
            pq.push(make_pair(-dist, make_pair(p1, p2)));
        }
    }
    for (int j = 0; j < m; j++)
    {
        vector<P> temp;
        for (int i = 0; i < n; i++)
        {
            if (map[i][j] == 0)
                continue;
            temp.push_back(link[i][j]);
        }
        for (int i = 1; i < temp.size(); i++)
        {
            P p1 = temp[i - 1];
            P p2 = temp[i];
            int dist = p2.first - p1.first - 1;
            pq.push(make_pair(-dist, make_pair(p1, p2)));
        }
    }

    long long ans = 0;
    while (!pq.empty())
    {
        int dist = -pq.top().first;
        P p1 = pq.top().second.first;
        P p2 = pq.top().second.second;
        pq.pop();

        if (do_find(p1) != do_find(p2))
        {
            if (dist == 0)
                do_union(p1, p2);
            else if (dist == 1)
                continue;
            else
            {
                ans += dist;
                do_union(p1, p2);
            }
        }
    }

    P root = pair(-1, -1);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (map[i][j] == 0) continue;
            if (root == pair(-1, -1)) root = do_find(pair(i, j));
            if (root != do_find(pair(i, j))) ans = -1;
        }
    }
    cout << ans;

    return 0;
}