Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
算法大牛帮忙看看我的prim,wa了一天半了用kruskal 47MS过了,用prim弄了一天半了还是WA ,大牛们帮忙看看吧! #include<iostream> #include <cmath> using namespace std; int n,a[102],p[102],c[102][102],sum=0; bool flag[102][102]; void makeset() //p[i]表根节点 { for(int i=1;i<=n;i++) { p[i]=i; } } int findset(int a) //返回根节点 { while(a!=p[a]) a=p[a]; return a; } void unionset(int a,int b)//连接 { if(a==b) return; if(a > b) swap(a,b); int x = b; for(int i=b; i<=n; i++) //将a与b所在链接起,即p[i]改为相等 if(p[i] == x) p[b] = a; } int min_V(int k) //选出与已选点a[]相连的边中的最小边的顶点 { int min_v=0; int min_e=1001; for(int i=0; i<=k; i++) for(int j=1; j<=n; j++) { if(a[i]==j || flag[a[i]][j]==true) //同一点和已连接的过 continue; if(findset(a[i]) == findset(j)) //形成回路的过 continue; if (c[a[i]][j] < min_e) //在与已选点a[]相连的边中选最小的 { min_e = c[a[i]][j]; min_v = j; } } flag[a[k]][min_v] = true; //标记已连接的 flag[min_v][a[k]] = true; unionset(a[k],min_v); //连接 sum += min_e; return min_v; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&c[i][j]); int p; scanf("%d",&p); memset(flag,false,sizeof(flag)); //memset() 库函数置初值 for(int k=0;k<p;k++) //改已连接的边为0,当成无连接的边处理 { int a,b; scanf("%d%d",&a,&b); c[a][b] = 0; c[b][a] = 0; } makeset(); //建立根节点 a[0] = 1; for(int t=1; t<n; t++) a[t] = min_V(t-1); //选点 cout<<sum<<endl; } /* 3 0 990 692 990 0 179 692 179 0 1 1 2 */ /* 4 0 5 6 7 5 0 8 1 6 8 0 3 7 1 3 0 1 2 3 */ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator