poj 2421

裸kruskal，算法大致是：
对每条边排序，从小到大。如果每次选取的边起点和终点在一个连通分量里，这条边将不会被加入，否则成环。
把题目中已经建立好路径的边用flag数组标记，并把边权改为0。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAX 110
#define INF 0x3f3f3f3f

using namespace std;

int n, q;
int map[MAX][MAX];
int Fa[MAX];
int flag[MAX][MAX];
int t;
struct Edge {
int s, e, len;
} edge[MAX * MAX];

bool cmp(const Edge &a, const Edge &b) { return a.len < b.len; }
int find(int x) {
if (x != Fa[x])
  return find(Fa[x]);
else
  return x;
}
bool Union(int x, int y) {
int fax = find(x);
int fay = find(y);
if (fax == fay)
  return false;

else {
  Fa[fax] = fay;
  return true;
}
}
int kruskal() {
int sum = 0;
sort(edge, edge + t, cmp);
for (int i = 0; i < n; i++)
  Fa[i] = i;

for (int i = 0; i < t; i++) {
  if (Union(edge[i].s, edge[i].e))
    sum += edge[i].len;
}

return sum;
}

int main() {
while (~scanf("%d", &n)) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      scanf("%d", &map[i][j]);
    }
  }
  scanf("%d", &q);
  int s, e;
  memset(flag, 0, sizeof(flag));
  for (int i = 0; i < q; i++) {
    scanf("%d%d", &s, &e);
    flag[s - 1][e - 1] = 1;
  }
  t = 0;
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      if (flag[i][j]) {
        edge[t].s = i;
        edge[t].e = j;
        edge[t++].len = 0;
      } else

      {
        edge[t].s = i;
        edge[t].e = j;
        edge[t++].len = map[i][j];
      }
    }
  }
  printf("%d\n", kruskal());
}

return 0;
}