图论-最小生成树-一些习题

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

图论-最小生成树-一些习题

作者：

豆浆灬油条 , 2020-03-30 18:18:55 , 所有人可见 , 阅读 833

1

5

模板题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 30;

int g[N][N], n, k, d[N];
bool st[N];

int prim()
{
    memset(st, 0, sizeof st);
    memset(d, 0x3f, sizeof d);
    d[0] = 0;
    int res = 0;

    for(int i = 1; i <= n; i ++){
        int t = -1;
        for(int j = 0; j < n; j ++)
            if(!st[j] && (t == -1 || d[j] < d[t]))
                t = j;

        st[t] = 1;
        res += d[t];

        for(int j = 0; j < n; j ++)
            d[j] = min(d[j], g[t][j]);
    }

    return res;
}

int main()
{
    while(cin >> n, n){
        memset(g, 0x3f, sizeof g);
        for(int i = 1; i < n; i ++){
            char s;
            cin >> s >> k;
            for(int j = 1; j <= k; j ++){
                char x;
                int w;
                cin >> x >> w;
                g[s - 'A'][x - 'A'] = g[x - 'A'][s - 'A'] = w;
            }
        }

        int res = prim();

        cout << res << endl;
    }
    return 0;
}

POJ - 1287

Kruskal 模板题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100;

int g[N][N], d[N], n, m;
bool st[N];

int prim()
{
    memset(d, 0x3f ,sizeof d);
    memset(st, 0, sizeof st);
    d[1] = 0;
    int res = 0;

    for(int i = 1; i <= n; i ++){
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || d[j] < d[t]))
                t = j;

        st[t] = 1;
        res += d[t];

        for(int j = 1; j <= n; j ++)
            d[j] = min(d[j], g[t][j]);
    }
    return res;
}

int main()
{
    while(cin >> n >> m, n){
        memset(g, 0x3f, sizeof g);
        for(int i = 1; i <= m; i ++){
            int a, b, c;
            cin >> a >> b >> c;
            g[a][b] = g[b][a] = min(g[a][b], c);
        }

        int res = prim();

        cout << res << endl;
    }
    return 0;
}

POJ - 2421

已经修好的边就将边权改为 0，最后对 n 个点跑一次最小生成树

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 110;

int g[N][N], d[N], n, m;
bool st[N];

int prim()
{
    memset(d, 0x3f ,sizeof d);
    memset(st, 0, sizeof st);
    d[1] = 0;
    int res = 0;

    for(int i = 1; i <= n; i ++){
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || d[j] < d[t]))
                t = j;

        st[t] = 1;
        res += d[t];

        for(int j = 1; j <= n; j ++)
            d[j] = min(d[j], g[t][j]);
    }

    return res;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            scanf("%d", &g[i][j]);
    cin >> m;
    for(int i = 1; i <= m; i ++){
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = 0;
    }

    int res = prim();

    cout << res << endl;

    return 0;
}

ZOJ - 1586

两个点之间的边权是自身的边权加上两个点的点权，那么就将两个点权加上之后做一遍最小生成树即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int g[N][N], d[N], T, n, a[N];
bool st[N];

int prim()
{
    memset(d, 0x3f, sizeof d);
    memset(st, 0, sizeof st);
    d[1] = 0;
    int res = 0;

    for(int i = 1; i <= n; i ++){
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || d[j] < d[t]))  t = j;

        st[t] = 1;
        res += d[t];

        for(int j = 1; j <= n; j ++)    d[j] = min(d[j], g[t][j]);
    }

    return res;
}

int main()
{
    cin >> T;
    while(T --){
        memset(g, 0x3f, sizeof g);
        cin >> n;
        for(int i = 1; i <= n; i ++)    scanf("%d", &a[i]);
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                scanf("%d", &g[i][j]), g[i][j] += a[i] + a[j];

        int res = prim();

        cout << res << endl;
    }

    return 0;
}

POJ - 1789

每两个字符串之间连边，边权值为两个字符串之间不同的字符数量。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 2010;

int g[N][N], d[N], n;
bool st[N];
char s[N][8];

int get(char a[], char b[])
{
    int res = 0;
    for(int i = 0; i < 7; i ++)
        if(a[i] != b[i])
            res ++;
    return res;
}

int prim()
{
    memset(d, 0x3f, sizeof d);
    memset(st, 0, sizeof st);
    d[1] = 0;
    int res = 0;

    for(int i = 1; i <= n; i ++){
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || d[j] < d[t]))  t = j;

        st[t] = 1;
        res += d[t];

        for(int j = 1; j <= n; j ++)    d[j] = min(d[j], g[t][j]);
    }

    return res;
}

int main()
{
    while(cin >> n, n){
        for(int i = 1; i <= n; i ++)    scanf("%s", s[i]);

        for(int i = 1; i <= n; i ++)
            for(int j = i + 1; j <= n; j ++)
                g[i][j] = g[j][i] = get(s[i], s[j]);

        int res = prim();

        printf("The highest possible quality is 1/%d.\n", res);
    }

    return 0;
}

POJ - 1258

模板题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 110;

int g[N][N], d[N], n;
bool st[N];

int prim()
{
    memset(d, 0x3f ,sizeof d);
    memset(st, 0, sizeof st);
    d[1] = 0;
    int res = 0;

    for(int i = 1; i <= n; i ++){
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || d[j] < d[t]))  t = j;

        st[t] = 1;
        res += d[t];

        for(int j = 1; j <= n; j ++)    d[j] = min(d[j], g[t][j]);
    }

    return res;
}

int main()
{
    while(cin >> n){
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                scanf("%d", &g[i][j]);

        cout << prim() << endl;        
    }

    return 0;
}

HDU - 1233

模板题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 110, M = N * (N - 1) / 2;

int f[N], n, m;
struct node{
    int a, b, c;
    bool operator < (node t) const{
        return c < t.c;
    }
}g[M];

int find(int x)
{
    if(x != f[x])   f[x] = find(f[x]);
    return f[x];
}

int main()
{
    while(cin >> n , n){
        m = n * (n - 1) / 2;
        for(int i = 1; i <= m; i ++){
            int a, b, c;
            cin >> a >> b >> c;
            g[i] = {a, b, c};
        }

        for(int i = 1; i <= n; i ++)    f[i] = i;
        sort(g + 1, g + 1 + m);

        long long res = 0;
        for(int i = 1; i <= m; i ++){
            int a = find(g[i].a), b = find(g[i].b), w = g[i].c;
            if(a != b){
                f[a] = b;
                res += w;
            }
        }
        cout << res << endl;
    }
    return 0;
}

HDU - 1875

只保留边权在 10 ~ 1000 之间的边，最后判断能否出现最小生成树

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;
typedef pair < double , double > pdd;
#define x first
#define y second

const int N = 110, M = N * N;
const double inf = 1e8;

pdd q[N];
int T, n, m, f[N];
struct node{
    int a, b;
    double w;
    bool operator < (node t) const{
        return w < t.w;
    }
}g[M];

double q_dis(pdd a, pdd b)
{
    int nx = a.x - b.x;
    int ny = a.y - b.y;
    return sqrt(nx * nx + ny * ny);
}

int find(int x)
{
    if(x != f[x])   f[x] = find(f[x]);
    return f[x];
}

int main()
{
    cin >> T;
    while(T --){
        cin >> n;
        m = 0;
        for(int i = 1; i <= n; i ++)
            f[i] = i;

        for(int i = 1; i <= n; i ++)
            cin >> q[i].x >> q[i].y;
        for(int i = 1; i <= n; i ++)
            for(int j = i + 1; j <= n; j ++){
                double z = q_dis(q[i], q[j]);
                if(10.0 <= z && z <= 1000.0)
                    g[m ++] = {i, j, z};
            }
        sort(g, g + m);
        int sum = 0;
        double res = 0.0;

        for(int i = 0; i < m; i ++){
            int a = g[i].a, b = g[i].b;
            double w = g[i].w;
            a = find(a), b = find(b);
            if(a != b){
                f[a] = b;
                sum ++;
                res += w;
            }
        }
        if(sum != n - 1)    puts("oh!");
        else    printf("%.1lf\n", res * 100.0);
    }
    return 0;
}

POJ - 3026

从s出发去寻找到达A的最短路径。如找到一个A，那么可以从当前位置出发这时候步数又为0了，又去寻找其他的A。

可以将每一个 S 或者 A 看成是一个点，从每一个 S 或者 A 出发，然后到达其他点的最短路径看成是一条边，最后建一颗最小生成树。

建图可以通过 BFS 求解每个点到其它字母的路径长度来获得边权。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;
typedef pair < int , int > pii;
#define x first
#define y second

const int N = 55, M = 110 * 110;

char g[N][N];
int n, m, T, f[M], num, d[N][N], k;
struct node{
    int a, b, w;
    bool operator < (node t) const{
        return w < t.w;
    }
}edg[M];
vector < pii > qu;
bool st[N][N];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int find(int x)
{
    if(x != f[x])   f[x] = find(f[x]);
    return f[x];
}

void bfs()
{
    for(int i = 0; i < qu.size(); i ++){
        memset(d, 0, sizeof d);
        memset(st, 0, sizeof st);
        pii t = qu[i];
        d[t.x][t.y] = 0;
        queue < pii > q;
        q.push({t.x, t.y});
        st[t.x][t.y] = 1;
        while(q.size()){
            pii t = q.front();q.pop();

            for(int j = 0 ; j < 4; j ++){
                int nx = t.x + dx[j], ny = t.y + dy[j];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m)  continue;
                if(st[nx][ny] || g[nx][ny] == '#')  continue;

                st[nx][ny] = 1;
                d[nx][ny] = d[t.x][t.y] + 1;
                q.push({nx, ny});
            }
        }

        for(int j = 0; j < qu.size(); j ++){
            if(i == j)  continue;
            pii t = qu[j];
            int z = d[t.x][t.y];
            edg[k ++] = {i, j, z};
        }
    }
}

int main()
{
    cin >> T;
    while(T --){
        num = k = 0;
        qu.clear();
        cin >> m >> n;
        gets(g[0]);
        for(int i = 0; i < n; i ++) gets(g[i]);

        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
                if(g[i][j] == 'A' || g[i][j] == 'S'){
                    qu.push_back({i, j});
                }
        num = qu.size();

        bfs();

        for(int i = 0; i <= num; i ++)  f[i] = i;
        sort(edg, edg + k);
        long long res = 0;
        for(int i = 0; i < k; i ++){
            int a = edg[i].a, b = edg[i].b, w = edg[i].w;
            // cout << a << " " << b << " " << w << endl;
            a = find(a), b = find(b);
            if(a != b){
                f[a] = b;
                res += w;
            }
        }
        cout << res << endl;
    }

    return 0;
}

POJ - 2031

三维最小生成树，相交的情况下，边权要赋值成0

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 110, M = N * N;

struct node{
    int a, b;
    double w;
    bool operator < (node t) const{
        return w < t.w;
    }
}g[M];
double x[N], y[N], z[N], c[N];
int f[N], n, k;

double q_dis(double x1, double y1, double z1, double x2, double y2, double z2)
{
    double nx = x1 - x2;
    double ny = y1 - y2;
    double nz = z1 - z2;
    return sqrt(nx * nx + ny * ny + nz * nz);
}

int find(int x)
{
    if(x != f[x])   f[x] = find(f[x]);
    return f[x];
}

int main()
{
    while(cin >> n, n){
        k = 0;
        for(int i = 1; i <= n; i ++){
            cin >> x[i] >> y[i] >> z[i] >> c[i];
            f[i] = i;
        }

        for(int i = 1; i <= n; i ++)
            for(int j = i + 1; j <= n; j ++){
                double w = q_dis(x[i], y[i], z[i], x[j], y[j], z[j]) - c[i] - c[j];
                if(w <= 0.0){
                    g[k].a = i;
                    g[k].b = j;
                    g[k ++].w = 0.0; 
                }else{
                    g[k].a = i;
                    g[k].b = j;
                    g[k ++].w = w;
                }
            }

        sort(g, g + k);

        double res = 0.0;
        for(int i = 0; i < k; i ++){
            int a = find(g[i].a), b = find(g[i].b);
            double w = g[i].w;
            if(a != b){
                f[a] = b;
                res += w;
            }
        }
        printf("%.3lf\n", res);
    }

    return 0;
}

POJ - 1751

最小生成树中，一些边已经连上。求剩余边连起来的最小生成树。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;
typedef long long ll;

const int N = 760, M = N * N;

int f[N], n, m, k;
struct node{
    int a, b;
    double w;
    bool operator < (node t) const{
        return w < t.w;
    }
}g[M];
long long x[N], y[N];

int find(int x)
{
    if(x != f[x])   f[x] = find(f[x]);
    return f[x];
}

double q_dis(ll x1, ll y1, ll x2, ll y2)
{
    double nx = x1 - x2;
    double ny = y1 - y2;
    return sqrt(nx * nx + ny * ny);
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)    scanf("%lld %lld", &x[i], &y[i]);
    for(int i = 1; i <= n; i ++)
        for(int j = i + 1; j <= n; j ++){
            double z = q_dis(x[i], y[i], x[j], y[j]);
            g[k ++] = {i, j, z};
        }
    cin >> m;
    for(int i = 1; i <= n; i ++)    f[i] = i;    
    for(int i = 1; i <= m; i ++){
        int a, b;
        scanf("%d%d", &a, &b); 
        a = find(a), b = find(b);
        if(a != b)
            f[a] = b;
    }

    sort(g, g + k);
    for(int i = 0; i < k; i ++){
        int a = find(g[i].a), b = find(g[i].b);
        double w = g[i].w;
        if(a != b){
            f[a] = b;
            if(w > 0)   printf("%d %d\n", g[i].a, g[i].b);
        }
    }
    return 0;
}

POJ - 2349

需要 n 个点连通起来，同时可以将 s 条边的边权变成 0。那就建立最小生成树，同时将边权从大到小排序，去掉前 s 条边

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;
typedef long long ll;

const int N = 510, M = N * N;

struct node{
    int a, b;
    double w;
    bool operator < (node t) const{
        return w < t.w;
    }
}g[M];
int f[N], n, k, T;
ll x[N], y[N];
double res[M];

int find(int x)
{
    if(x != f[x])   f[x] = find(f[x]);
    return f[x];
}

double q_dis(ll x1, ll y1, ll x2, ll y2)
{
    double nx = x1 - x2;
    double ny = y1 - y2;
    return sqrt(nx * nx + ny * ny);
}

int main()
{
    cin >> T;
    while(T --){
        cin >> k >> n;
        int m = 0;
        for(int i = 1; i <= n; i ++)    scanf("%lld %lld", &x[i], &y[i]);

        for(int i = 1; i <= n; i ++)
            for(int j = i + 1; j <= n; j ++){
                double z = q_dis(x[i], y[i], x[j], y[j]);
                g[m ++] = {i, j, z};
            }

        for(int i = 1; i <= n; i ++)    f[i] = i;

        sort(g, g + m);

        int sum = 0;
        for(int i = 0; i < m; i ++){
            int a = find(g[i].a), b = find(g[i].b);
            double w = g[i].w;

            if(a != b){
                f[a] = b;
                res[++ sum] = w;
            }
        }

        sort(res + 1, res + 1 + sum);
        reverse(res + 1, res + 1 + sum);
        printf("%.2f\n", res[k]);
    }

    return 0;
}

2 评论

AmazingL 2023-03-14 20:58

666

左手影视 2020-03-30 18:20

tql

App 内打开