prim最小生成树算法题poj2485

开始想用kruskal算法自己写写runtime error

#include<cstdio>
#include<queue>
#include<set>
using namespace std;
int a[2510][25100];
struct weight
{
int a,b;
int value;
bool operator < (const weight & rhs) const
{
return value < rhs.value;
}
bool operator > (const weight & rhs) const
{
return value > rhs.value;
}
};
int sett[251000];

int find2(int x)
{
while(x != sett[x]) x=sett[x];
return x;
}
void merge2(int a,int b)
{
if(a > b) sett[a]=b;
else sett[b]=a;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
priority_queue<weight , vector<weight> , greater<weight> > pq;
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) sett[i]=i;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
int x;
scanf("%d",&x);
if(x == 0) x = 65537;
weight route;
route.a=i;
route.b=j;
route.value=x;
pq.push(route);
}


set<int> drop;

// printf("size=%d n=%d\n",drop.size(),n);
while(drop.size() != n-1){
// printf("size=%d n=%d\n",drop.size(),n);
weight mi = pq.top();
pq.pop();
int fx =find2(mi.a);
int fy =find2(mi.b);

if(fx!=fy){
drop.insert(mi.value);
merge2(fx,fy);
}


}
// printf("size%d\n",drop.size() );
// for(set<int>::iterator it=drop.begin();it!=drop.end();it++){
// printf("dsa\n");
// printf("%d ",*it);
// }
set<int>::iterator it = drop.end();
it--;
printf("%d\n",*it );





}
return 0;
}
/*
1
4
0 1 2 3
1 0 2 3
2 2 0 3
3 3 3 0

-1073741819
-1073741819
*/

然后写的prim算法

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int cost[510][510];
int mincost[510];
bool used[510];
int n;
int prim()
{
memset(used,false,sizeof(used));
memset(mincost,65537,sizeof(mincost));
int MAXres=0;
mincost[0]=0;
while(true){
int v=-1;
for(int i=0;i<n;i++)
if(!used[i] && ( v==-1 || mincost[i]<mincost[v]) ) v=i;
if(v == -1) break;
used[v]=true;

if(mincost[v] >MAXres)MAXres=mincost[v];
for(int i=0;i<n;i++)
mincost[i] = min(mincost[i], cost[v][i]);
}
return MAXres;
}
int main()
{
int cases;
scanf("%d",&cases);
while(cases--){

scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
int x;
scanf("%d",&cost[i][j]);
if(cost[i][j]== 0) cost[i][j] = 65537;
}
printf("%d\n",prim());

}

return 0;
}