H - Highways——最小生成树Kruskal算法+Prim算法-蒲公英云

H - Highways——最小生成树Kruskal算法+Prim算法

水深无声 2022-06-11 07:18 325阅读 0赞

Think:
1知识点：最小生成树Kruskal算法+Prim算法
2思考：
1>多组输入超时，单组输入AC——why???
2>排序时结构体内重载小于号快于再单独写cmp判断函数
3题意：需要使得n个结点构成连通图，已知有m个结点已经连接，询问最小花费构成连通图还需要连接那些结点
4思路：
1>Kruskal算法：先预处理所有结点距离，预处理结点距离时将其入队，之后按照权值排序，然后在通过并查集将已经连接的结点连成集合，记录有效边，进而按照已经排序的顺序更新试探，直到连接n个结点
2>Prim算法：先预处理所有结点距离，构造二维地图，然后通过已经连接的结点更新地图(可将地图中已经连接的结点预处理边权为0)，进而Prim算法即可

vjudge题目链接

以下为Accepted代码——Prim算法-79ms

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
struct Node{
    int x, y;
}node[1014];
struct Dist{
    int u;
    int w;
}dis[1014];
int vis[1014], e[1014][1014];
void Prim(int n);
int Dis(int u, int v);
int main(){
    int n, m, i, j, u, v;
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
        scanf("%d %d", &node[i].x, &node[i].y);
    for(i = 1; i <= n; i++){
        for(j = i+1; j <= n; j++){
            e[i][j] = e[j][i] = Dis(i, j);
        }
    }
    scanf("%d", &m);
    while(m--){
        scanf("%d %d", &u, &v);
        e[u][v] = e[v][u] = 0;
    }
    Prim(n);
    return 0;
}
int Dis(int u, int v){
    int dx = node[u].x - node[v].x;
    int dy = node[u].y - node[v].y;
    int dl = dx*dx + dy*dy;
    return dl;
}
void Prim(int n){
    int i, miv, v, num;
    memset(vis, 0, sizeof(vis));
    for(i = 1; i <= n; i++){
        dis[i].w = e[1][i];
        dis[i].u = 1;
    }
    vis[1] = 1, dis[1].w = 0, num = 1;
    while(num < n){
        miv = inf;
        for(i = 1; i <= n; i++){
            if(!vis[i] && dis[i].w < miv){
                miv = dis[i].w, v = i;
            }
        }
        vis[v] = 1, num++;
        if(e[v][dis[v].u])
            printf("%d %d\n", dis[v].u, v);
        for(i = 1; i <= n; i++){
            if(!vis[i] && e[v][i] < dis[i].w){
                dis[i].w = e[v][i];
                dis[i].u = v;
            }
        }
    }
}

以下为Time Limit Exceeded代码——Kruskal算法-排序：单独写cmp判断函数

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double zero = 1e-4;
struct Edge{
    int u;
    int v;
    int w;
}edge[501400];
struct Node{
    int x;
    int y;
}node[1014];
bool cmp(struct Edge a, struct Edge b){
    return a.w < b.w;
}
int tp, f[1014];
void Init(int n);
int get_f(int v);
bool Merge(int u, int v);
double Dis(int i, int j);
int main(){
    int n, m, i, j, t, num, u, v;
    scanf("%d", &n);
        Init(n);
        for(i = 1; i <= n; i++){
            scanf("%d %d", &node[i].x, &node[i].y);
        }
        t = 0;
        for(i = 1; i <= n; i++){
            for(j = i+1; j <= n; j++){
                edge[t].u = i, edge[t].v = j;
                edge[t].w = Dis(i, j);
                t++;
            }
        }
        sort(edge, edge+t, cmp);
        num = 0;
        scanf("%d", &m);
        while(m--){
            scanf("%d %d", &u, &v);
            if(Merge(u, v))
                num++;
        }
        for(i = 0; i < t; i++){
            u = edge[i].u, v = edge[i].v;
            if(Merge(u, v)){
                printf("%d %d\n", u, v);
                num++;
            }
            if(num == n-1)
                break;
        }
    return 0;
}
void Init(int n){
    for(int i = 1; i <= n; i++)
        f[i] = i;
}
double Dis(int i, int j){
    int dx = node[i].x - node[j].x;
    int dy = node[i].y - node[j].y;
    int xy = dx*dx + dy*dy;
    return xy;
}
bool Merge(int u, int v){
    int t1 = get_f(u);
    int t2 = get_f(v);
    if(t1 != t2){
        f[t2] = t1;
        return true;
    }
    else
        return false;
}
int get_f(int v){
    if(f[v] == v)
        return f[v];
    f[v] = get_f(f[v]);
    return f[v];
}

以下为Accepted代码——Kruskal算法-454ms-排序：结构体内重载小于号

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double zero = 1e-4;
struct Edge{
    int u;
    int v;
    int w;
    bool operator < (const Edge &b)const{
        return w < b.w;
    }
}edge[501400];
struct Node{
    int x;
    int y;
}node[1014];
int tp, f[1014];
void Init(int n);
int get_f(int v);
bool Merge(int u, int v);
double Dis(int i, int j);
int main(){
    int n, m, i, j, t, num, u, v;
    scanf("%d", &n);
        Init(n);
        for(i = 1; i <= n; i++){
            scanf("%d %d", &node[i].x, &node[i].y);
        }
        t = 0;
        for(i = 1; i <= n; i++){
            for(j = i+1; j <= n; j++){
                edge[t].u = i, edge[t].v = j;
                edge[t].w = Dis(i, j);
                t++;
            }
        }
        sort(edge, edge+t);
        num = 0;
        scanf("%d", &m);
        while(m--){
            scanf("%d %d", &u, &v);
            if(Merge(u, v))
                num++;
        }
        for(i = 0; i < t; i++){
            u = edge[i].u, v = edge[i].v;
            if(Merge(u, v)){
                printf("%d %d\n", u, v);
                num++;
            }
            if(num == n-1)
                break;
        }
    return 0;
}
void Init(int n){
    for(int i = 1; i <= n; i++)
        f[i] = i;
}
double Dis(int i, int j){
    int dx = node[i].x - node[j].x;
    int dy = node[i].y - node[j].y;
    int xy = dx*dx + dy*dy;
    return xy;
}
bool Merge(int u, int v){
    int t1 = get_f(u);
    int t2 = get_f(v);
    if(t1 != t2){
        f[t2] = t1;
        return true;
    }
    else
        return false;
}
int get_f(int v){
    if(f[v] == v)
        return f[v];
    f[v] = get_f(f[v]);
    return f[v];
}