| ||||||||||
| 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