poj 写最小生成树！1258 2458（类似）

poj 1258

kruskal:

#include<iostream>
#include<string.h>

#include<algorithm>
using namespace std;
struct tree{
 int u,v;
 int w;
}edge[100005];//这里如果开太小会RE的
int father[100005],vis[100005],temp;
bool cmp(tree a,tree b){
 return a.w<b.w;
}
int find(int son){
 while(son!=father[son])
  son=father[son];
 return son;
}
void combine(int ra,int rb){
 if(ra!=rb)
  father[ra]=father[rb];
}
int main(){
 int n,i,k,t;
 while(scanf("%d",&n)!=EOF&&n){
  memset(vis,0,sizeof(vis));
  for(i=0;i<100005;i++)
   father[i]=i;
  for(i=1,t=0;i<=n;i++)
   for(k=1;k<=n;k++){
    scanf("%d",&temp);
    if(i!=k&&k>i){
     edge[t].u=i;edge[t].v=k;edge[t].w=temp;
     t++;
    } 
   }
   sort(edge,edge+t,cmp);
   int ans=0;
   for(i=0;i<t;i++){
    int x=find(edge[i].u);int y=find(edge[i].v);
    if(x!=y){
     ans+=edge[i].w;
     combine(x,y);
    }
   }
   printf("%d/n",ans);
 }
 return 0;
}

 

 

prime(不是很熟):

#include <iostream>
using namespace std;
int main()
{
    int n,t,a[105][105],i,j,sign[105];//记录可取值的行。
    while(cin>>n)
    {
        int min,ans=0,cm;
        for(i=0;i<n;i++)
        {
            sign[i]=0;
            for(j=0;j<n;j++)
            {
                cin>>a[i][j];
            }
        }
        t=n-1;sign[0]=1;//原点已取，所以sign[0]=1
        for(i=0;i<n;i++)//将第一列归0.
   a[i][0]=0;
        while(t--)
        {
           min=100000;
           for(i=0;i<n;i++)
           {
               if(sign[i])
               {
                   for(j=0;j<n;j++)
                   {
                      if(a[i][j]>0&&a[i][j]<min)
                       {min=a[i][j];cm=j;}//求最短的边，并记录所在的列。
                   }
               }
           }
           ans+=min;
           for(i=0;i<n;i++)//将取过点的列归零
           a[i][cm]=0;
           sign[cm]=1;//将取过点的那行 归为可取值的行。
        }
        cout<<ans<<endl;
    }
    return 0;
}