求最小生成树。有一点点的变化，就是有的边已经给出来了。所以，最小生成树里面必须有这些边，kruskal和prim算法都能够，prim更简单一些。有一点须要注意，用克鲁斯卡尔算法的时候须要将已经存在的边预处理一下，并查集转化为同一个祖先。记得要找他们的祖先再转化。普里姆算法仅仅须要将那些已经存在的边都初始化为0就能够了。
kruskal：
#include#include #include #include #define MAX 0x7fffffffusing namespace std;struct node{ int i,j,len;}gra[10005];int p[105];int n;int cmp(const void *a,const void *b){ return ((node *)a)->len - ((node *)b)->len;}int find(int x){ return p[x] == x? x: (p[x] = find(p[x]));}void kruskal(){ int i,sum = 0; for(i=1; i<=n*n; i++) { int x = find(gra[i].i); int y = find(gra[i].j); if(x != y) { sum += gra[i].len; p[x] = y; } } cout << sum << endl; return ;}int main(){ int i,j,m,c; while(cin >> n) { int k = 1; for(i=1; i<=n; i++) for(j=1; j<=n; j++) { cin >> c; gra[k].i = i; gra[k].j = j; gra[k].len = c; k ++; } cin >> m; for(i=1; i<=n; i++) p[i] = i; int a ,b; for(i=1; i<=m; i++) { cin >> a >> b; a = find(a);//注意这里。wa了几次。。。要找他们的祖先。。
。 b = find(b); p[a] = b; } qsort(gra+1,k-1,sizeof(gra[0]),cmp); kruskal(); } return 0; }
prim：
#include#include #include #include #define MAX 0x7fffffffusing namespace std;int gra[105][105];int n;void prim(){ int visit[105],now,i,j; int d[105]; memset(visit,0,sizeof(visit)); for(i=1; i<=n; i++) d[i] = MAX; now = 1;visit[1] = 1; d[1] = 0; for(i=1; i<=n; i++) { for(j=1; j<=n; j++) if(!visit[j] && d[j]>gra[now][j]) d[j] = gra[now][j]; int MIN = MAX; for(j=1; j<=n; j++) { if(!visit[j] && MIN > d[j]) MIN = d[now=j]; } visit[now] = 1; } int sum = 0; for(j=1; j<=n; j++) sum += d[j]; cout << sum << endl; return ;}int main(){ int i,j,c; while(cin >> n) { for(i=1; i<=n; i++) for(j=1; j<=n; j++) { cin >> c; gra[i][j] = c; } int m,a,b; cin >> m; for(i=1; i<=m; i++) { cin >> a >> b; gra[a][b] = gra[b][a] = 0; } prim(); } return 0; }