H - Highways - poj 1751（prim）

某个地方政府想修建一些高速公路使他们每个乡镇都可以相同通达，不过以前已经修建过一些公路，现在要实现所有的联通，所花费的最小代价是多少？（也就是最小的修建长度），输出的是需要修的路，不过如果不需要修建就什么都不输出。

分析：构建一个完全图，使用krusal进行一些简单优化不知道可以不，试一下吧

已经T成狗了

下面是TLE的krusal代码

******************************************************************************

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#include<math.h>

#include<vector>

#include<algorithm>

using namespace std;

#define maxn 1005

int f[maxn];

struct node{

    int u, v;double len;

    friend bool operator < (node a, node b){

        return a.len > b.len;

    }

};

struct point{int x, y;}p[maxn], ans[maxn];

double Len(point a, point b){

    int x = a.x-b.x;

    int y = a.y-b.y;

    return sqrt(x*x+y*y);

}

int Find(int x)

{

    if(f[x] != x)

        f[x] = Find(f[x]);

    return f[x];

}

int Union(int x, int y)

{

    x = Find(x);

    y = Find(y);

    if(x != y)

    {

        f[x] = y;

        return 1;

    }

    return 0;

}

bool cmp(point a, point b)

{

    if(a.x != b.x)

        return a.x < b.x;

    return a.y < b.y;

}

int main()

{

    int N;

    scanf("%d", &N);

    int M, u, v, t=0, k=0;

    node s;

    priority_queue<node> Q;

    for(s.u=1; s.u<=N; s.u++)

    {

        f[s.u] = s.u;

        scanf("%d%d", &p[s.u].x, &p[s.u].y);

        for(s.v=1; s.v<s.u; s.v++)

        {

            s.len = Len(p[s.u], p[s.v]);

            Q.push(s);

        }

    }

    scanf("%d", &M);

    while(M--)

    {

        scanf("%d%d", &u, &v);

        t += Union(u, v);

    }

    while(Q.size() && t < N)

    {

        s = Q.top();Q.pop();

        if(Union(s.u, s.v) == 1)

        {

            t += 1;

            ans[k].x = s.v;

            ans[k++].y = s.u;

        }

    }

    for(int i=0; i<k; i++)

        printf("%d %d\n", ans[i].x, ans[i].y);

    return 0;

}

****************************************************************************

下面换成prim试一下吧

终于A掉了，使用优先队列会造成超内存

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#include<math.h>

#include<vector>

#include<algorithm>

using namespace std;

#define maxn 1005

#define oo 0xfffffff

double G[maxn][maxn];

struct point{int x, y;}p[maxn], ans[maxn];

struct node{int v;double len;}dist[maxn];

double Len(point a, point b){

    int x = a.x-b.x;

    int y = a.y-b.y;

    return sqrt(x*x+y*y);

}

void prim(int N)

{

    int i, use[maxn] = {0, 1};

    for(i=1; i<=N; i++)

        dist[i].v = 1, dist[i].len = G[1][i];

    for(i=1; i<N; i++)

    {

        int k=0;double Min = oo;

        for(int j=1; j<=N; j++)

        {

            if(!use[j] && Min > dist[j].len)

                Min = dist[j].len, k = j;

        }

        use[k] = true;

        for(int j=1; j<=N; j++)

        {

            if(!use[j] && k!=j && G[k][j] < dist[j].len)

                dist[j].len = G[k][j], dist[j].v = k;

        }

    }

}

int main()

{

    int i, j, N, M, u, v;

    scanf("%d", &N);

    for(i=1; i<=N; i++)

        scanf("%d%d", &p[i].x, &p[i].y);

    for(i=1; i<=N; i++)

    for(j=1; j<i; j++)

    {

        G[j][i] = G[i][j] = Len(p[i], p[j]);

    }

    scanf("%d", &M);

    while(M--)

    {

        scanf("%d%d", &u, &v);

        G[u][v] = G[v][u] = -1;

    }

    prim(N);

    for(int i=2; i<=N; i++)

    {

        if(dist[i].len > 0)

            printf("%d %d\n", i, dist[i].v);

    }

    return 0;

}