POJ 2421 Constructing Roads MST kruskal

最近剛學的并查集所以用kruskal來試試最小生成樹~

kruskal其實用幾句話就能說完~?

1.貪心所有邊的權值,從小到大取值

2.取值時~將邊權非0的兩個頂點~進行并查操作~如果兩個點的祖先不同...邊權加入最小生成樹...并且將兩個點納入同一個集合中

3.判斷是否所有點都在同一個集合中

完畢~

下面上代碼~這個代碼應該可以作為模版了...但是并查集沒有優化~所以復雜度約為0(n^3)但是比prim好一點

32ms水過...

mian()前的代碼修改一下可以作為kruskal的模版...我再寫一篇專門放模版吧~

#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
const int V = 101;
int father[V],map[V][V];
struct point 
{int s,v,rank;
}p[V*V];
int cmp(point a, point b)
{	return a.rank<b.rank;	
}
int find(int x)
{if(x!=father[x])father[x]=find(father[x]);return father[x];
}
void Union(int a,int b)
{int x = find(a);int y = find(b);if(x==y)	return ;father[y]=x;
}
bool found(int n)
{int x=find(0);for(int i=0;i<n;i++)if(find(i)!=x)return false;return true;
}
int kruskal(int map[][V],int n)
{int i,j,cnt,mst=0;for(i=0,cnt=0;i<n;i++){father[i]=i;for(j=0;j<n;j++){p[cnt].s=i;p[cnt].v=j;p[cnt].rank = map[i][j];cnt++;}}sort(p,p+n*n,cmp);for(i=0;i<n*n;i++){if(p[i].rank!=0 && p[i].rank!=-1){if(find(p[i].s)!=find(p[i].v))mst+=p[i].rank;Union(p[i].s,p[i].v);if(found(n)==true)return mst;}else if(p[i].rank==-1){Union(p[i].s,p[i].v);if(found(n)==true)return mst;}}	
}
int main()
{
//	freopen("in.txt","r",stdin);int n;scanf("%d",&n);int m,i,j,p,q,cnt=0;memset(map,0,sizeof(map));for(i=0;i<n;i++)for(j=0;j<n;j++)scanf("%d",&map[i][j]);cin>>m;while(m--){cin>>p>>q;map[p-1][q-1]=-1;}cout<<kruskal(map,n)<<endl;	return 0;
}