题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1102
题解：
纯最小生成树，只是有些边已经确定了要加入生成树中，特殊处理一下这些边就可以了。
kruskal算法：
由于有些边已经确定，所以在调用kruskal()之前，就把这条边的两个顶点放在一个集合就可以了。
#include<cstdio>//hdu1102 最小生成树 kruskal
#include<algorithm>
#define N 110
using namespace std; struct node
{
int x,y,dis;
}edge[N*N]; int fa[N]; bool cmp(node a, node b)
{
return a.dis<=b.dis;
} int find(int x)
{
return fa[x]==x?x:find(fa[x]);
} bool un(int x, int y)
{
x = find(x);
y = find(y);
if(x!=y)
{
fa[x] = y;
return true;
}
return false;
} int kruskal(int n,int sum)
{
int len = ,x,y,i;
sort(edge,edge+sum,cmp);
for(i = ; i<sum; i++)
{
x = edge[i].x;
y = edge[i].y;
if(un(x,y))
len += edge[i].dis;
}
return len;
} int main()
{
int n,m,i,j,x,y,dis,sum;
while(scanf("%d",&n)!=EOF)
{
sum = ;
for(i = ; i<=n; i++)
for(j = ; j<=n; j++)
{
scanf("%d",&dis);
if(i>=j) continue;
edge[sum].x = i;
edge[sum].y = j;
edge[sum].dis = dis;
sum++;
} for(i = ; i<=n; i++)
fa[i] = i; scanf("%d",&m);
for(i = ; i<m; i++)//先处理以确定的边
{
scanf("%d%d",&x,&y);
un(x,y);
}
printf("%d\n",kruskal(n,sum));
}
return ;
}
prim算法：
在prim算法中就不能像kruskal算法那样先预处理了，而要在算法中运行。由于prim算法在每次松弛时总是找最小的点，题目中两条村庄的距离是非负数，那么我们可以把确定要加入生成树的边的两个顶点的距离设为-1，这样就能确保他们都加入到生成树中了。
注意：赋值或修改邻接矩阵的无向图时， 正反两条边都要操作。
#include<cstdio>//hdu1102 最小生成树 prim
#include<algorithm>
#define N 110
#define INF 0x7fffffff
using namespace std; int arc[N][N]; int prim(int n)
{
int low[N];
int k,i,j,min,len = ;
for(i = ; i<=n; i++)
{
low[i] = arc[][i];
} for(i = ; i<=n; i++)
{
min = INF;
for(j = ; j<=n; j++)
{
if(low[j]!= && low[j]<min)
{
min = low[j];
k = j;
}
} if(low[k]>)
len += low[k];
low[k] = ; for(int j = ; j<=n; j++)
{
if(low[j]!= && arc[k][j]<low[j])
{
low[j] = arc[k][j];
}
}
}
return len;
} int main()
{
int n,q,u,v,i,j;
while(scanf("%d",&n)!=EOF)
{
for(i = ; i<=n; i++)
for(j = ; j<=n; j++)
scanf("%d",&arc[i][j]); scanf("%d",&q);
for(i = ; i<q; i++)
{
scanf("%d%d",&u,&v);
arc[v][u] = arc[u][v] = -;
//正反向都要置为-1， 因为在松弛的过程中，两个方向都有可能
}
printf("%d\n",prim(n));
}
return ;
}