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

分析:构建一个完全图,使用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;
}
04-25 19:48