poj-1751Highways(最小生成树)

题意：

给了n个点的坐标，给了m条已经相连的边。输出建成最小生成树的其他边。

思路：

简单,普通的建立，之所以要写这篇博客，是因为它动不动超内存。为了以后不踩坑，于是写篇博客警醒自己。

克鲁斯卡尔

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int M=600000;//之前一直以为是这个大了才超的内存，但是参考了一下大神的博客，发现不是这个的问题
struct node
{
    int a,b;
    double w;
} edge[M];
struct tree
{
    int a,b;
} point[800];//之前是用两数组存，但是超内存，发现是这个两个数组的问题
int n,m;
int root[800];
int find(int x)
{
    if(x==root[x])
    {
        return x;
    }
    else
    {
        return root[x]=find(root[x]);
    }
}
int ouin(int a,int b)
{
    int x=find(a);
    int y=find(b);
    if(x==y)
    {
        return 0;
    }
    else
    {
        root[x]=y;
        return 1;
    }

}
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int main( )
{
    int a,b;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        root[i]=i;
        scanf("%d%d",&point[i].a,&point[i].b);
    }
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)//我以前都是j=1开始，但是这次超时，逼成这样，以前知道这样可以，但是偷懒不想
        {
            edge[cnt].a=i;
            edge[cnt].b=j;
            edge[cnt++].w=(point[i].a-point[j].a)*(point[i].a-point[j].a)+(point[i].b-point[j].b)*(point[i].b-point[j].b);
        }
    }
    scanf("%d",&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&a,&b);
        edge[cnt].a=a;
        edge[cnt].b=b;
        edge[cnt++].w=0;
    }
    sort(edge,edge+cnt,cmp);
    int res=0;
    int ans=0;
    for(int i=0; i<cnt; i++)
    {
        if(ouin(edge[i].a,edge[i].b))
        {
            if(edge[i].w!=0)
            {
               cout<<edge[i].a<<" "<<edge[i].b<<endl;
            }
            res++;
        }
        if(res==n-1)
        {
            break;
        }
    }
    return 0;
}

Prim

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define INF 0x3f3f3f3f
using namespace std;
int mp[800][800];
struct node
{
    int a,b;
}point[800];
int vis[800];
int pre[800];//记录每个节点的父节点
int low[800];
void prim(int cost[ ][800],int n)
{
    memset(vis,0,sizeof(vis));
    int i,j;
    int pos=1;//父节点从1开始
    for(i=1;i<=n;i++)
    {
        low[i]=mp[i][1];
        pre[i]=pos;
    }
    vis[1]=1;
    for(int i=2;i<=n;i++)
    {
        int mi=INF;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&low[j]<mi)
            {
                mi=low[j];
                pos=j;
            }
        }
        if(mp[pre[pos]][pos])
        {
            cout<<pre[pos]<<" "<<pos<<endl;
        }
        vis[pos]=1;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&low[j]>cost[pos][j])
            {
                low[j]=cost[pos][j];//如果通过当前的节点pos到达节点j更近，意味着到达节点j必须经过节点pos，所以节点j的父节点就是pos
                pre[j]=pos;
            }
        }
    }
}
int add(int i,int j)
{
    return (point[i].a-point[j].a)*(point[i].a-point[j].a)+(point[i].b-point[j].b)*(point[i].b-point[j].b);

}
int main( )
{
    int n,m;
    int x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&point[i].a,&point[i].b);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            mp[i][j]=add(i,j);
        }
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        mp[x][y]=mp[y][x]=0;
    }
    prim(mp,n);
    return 0;
}