//Prim算法
#include <iostream>
#include <memory.h>
#define INF 1000000
#define MAX 200
using namespace std;
int main()
{
int arcs[MAX][MAX];
bool isvisit[MAX];
int min_weight[MAX];
int N, Q;
int x, y;
freopen("C:\\Users\\Haojian\\Desktop\\test.txt", "r", stdin);
while (cin >> N)
{
memset(isvisit, false, sizeof(isvisit));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> arcs[i][j];
cin >> Q;
for (int i = 0; i < Q; i++)
{
cin >> x >> y;
arcs[x-1][y-1] = arcs[y-1][x-1] = 0;
}
for (int i = 0; i < N; i++)
min_weight[i] = arcs[0][i];
isvisit[0] = true;
int _min, isallconnect;
int hold, result = 0;
for (int i = 1; i < N; i++)
{
_min = INF;
isallconnect = true;
for (int j = 0; j < N; j++)
{
if (!isvisit[j] && min_weight[j] < _min)
{
_min = min_weight[j];
hold = j;
}
}
result += _min;
isvisit[hold] = true;
for (int j = 0; j < N; j++)
if (!isvisit[j] && arcs[hold][j] < min_weight[j])
min_weight[j] = arcs[hold][j];
}
cout << result << endl;
}
return 0;
}
//kruskal算法 #include <iostream> #include <algorithm> #define MAX 200 using namespace std; int father[MAX]; int my_rank[MAX]; void make_set() { for (int i = 0; i < MAX; i++) { father[i] = i; my_rank[i] = 0; } } int find_set(int x) { if (x != father[x]) father[x] = find_set(father[x]); return father[x]; } void union_set(int x, int y) { x = find_set(x); y = find_set(y); if (x == y) return; if (my_rank[x] > my_rank[y]) father[y] = x; else { father[x] = y; if (my_rank[x] == my_rank[y]) my_rank[y]++; } } struct edge { int start; int end; int weight; }; bool cmp(const edge& a, const edge& b) { return a.weight < b.weight; } edge e[99*50+2]; int main() { int N, Q, count; int x, y, cost; while (cin >> N) { count = 0; make_set(); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { cin >> cost; if (j > i) { e[count].start = i; e[count].end = j; e[count++].weight = cost; } } } cin >> Q; for (int i = 0; i < Q; i++) { cin >> x >> y; x = find_set(x); y = find_set(y); if (x != y) union_set(x, y); } sort(e, e+count, cmp); N = count; count = 0; int sum = 0; while (count != N) { x = find_set(e[count].start); y = find_set(e[count].end); if (x != y) { union_set(x, y); sum += e[count].weight; } count++; } cout << sum << endl; } return 0; }