POJ 2421 Constructing Roads 最小生成树

题意：还是给你n个点，然后求最小生成树。特殊之处在于有一些点之间已经连上了边。
思路：对于已经有边的点，特殊标记一下，加边的时候把这些边的权值赋值为0即可。这样就可以既保证这些边一定存在，又保证了所求的结果正确。
代码：
[cpp] 
#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <string.h> 
#include <climits> 
using namespace std; 
 
#define CLR(arr,val) memset(arr,val,sizeof(arr)) 
const int N = 110; 
int father[N]; 
struct edge{ 
    int lp,rp,value; 
}ee[N*N]; 
int map[N][N],flag[N][N],numedge,n; 
bool cmp(edge a,edge b){ 
    return a.value < b.value; 
} 
int find(int x){ 
    if(x == father[x]) 
        return father[x]; 
    return find(father[x]); 
} 
bool Union_Set(int x,int y){ 
    int fx = find(x); 
    int fy = find(y); 
    if(fx == fy){ 
      return false; 
    } 
    else{ 
      father[fx] = fy; 
      return true; 
    } 
} 
int kruskal(){ 
    sort(ee,ee+numedge,cmp); 
    for(int i = 1; i <= n; ++i) 
        father[i] = i; 
    int sum = 0; 
    for(int i = 0; i < numedge; ++i){ 
        int lx = ee[i].lp; 
        int rx = ee[i].rp; 
        if(Union_Set(lx,rx)){ 
            sum += ee[i].value; 
        } 
    } 
    return sum; 
} 
int main(){ 
    //freopen("1.txt","r",stdin); 
    while(scanf("%d",&n) != EOF){ 
      CLR(flag,0); 
        for(int i = 1; i <= n; ++i){ 
          for(int j = 1; j <= n; ++j) 
              scanf("%d",&map[i][j]); 
        } 
        int m,x,y; 
        scanf("%d",&m); 
        while(m--){ 
          scanf("%d%d",&x,&y); 
          flag[x][y] = 1; 
        } 
        numedge = 0; 
        for(int i = 1; i < n; ++i){ 
            for(int j = i + 1; j <= n; ++j){ 
                if(flag[i][j]){ 
                    ee[numedge].lp = i; 
                    ee[numedge].rp = j; 
                    ee[numedge].value = 0; 
                    numedge++; 
                } 
                else{ 
                    ee[numedge].lp = i; 
                    ee[numedge].rp = j; 
                    ee[numedge].value = map[i][j]; 
                    numedge++; 
                } 
            } 
        } 
        int ans = kruskal(); 
        printf("%d\n",ans); 
    } 
    return 0; 
} 

补充：软件开发 , C++ ,