手机怎么在百度做网站,网页游戏网站首页,aws的efs可以做网站的什么,中国建设银行信用卡最近刚学的并查集所以用kruskal来试试最小生成树~ kruskal其实用几句话就能说完~ 1.贪心所有边的权值,从小到大取值 2.取值时~将边权非0的两个顶点~进行并查操作~如果两个点的祖先不同...边权加入最小生成树...并且将两个点纳入同一个集合中 3.判断是否所有点都在同一个集合中…最近刚学的并查集所以用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.rankb.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(xy) return ;father[y]x;
}
bool found(int n)
{int xfind(0);for(int i0;in;i)if(find(i)!x)return false;return true;
}
int kruskal(int map[][V],int n)
{int i,j,cnt,mst0;for(i0,cnt0;in;i){father[i]i;for(j0;jn;j){p[cnt].si;p[cnt].vj;p[cnt].rank map[i][j];cnt;}}sort(p,pn*n,cmp);for(i0;in*n;i){if(p[i].rank!0 p[i].rank!-1){if(find(p[i].s)!find(p[i].v))mstp[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,cnt0;memset(map,0,sizeof(map));for(i0;in;i)for(j0;jn;j)scanf(%d,map[i][j]);cinm;while(m--){cinpq;map[p-1][q-1]-1;}coutkruskal(map,n)endl; return 0;
}转载于:https://www.cnblogs.com/Felix-F/archive/2012/08/10/3223657.html
