---

title: poj-2421-最小生成树刷题

date: 2018-11-20 20:30:29

tags:

• acm
• 刷题
  
  categories:
• ACM-最小生成树

---

概述

做了几道最小生成树的题，，，都是些板子题，，，直接套板子就能过，，，有一些是在输入数据做文章，，处理一下再建图就行了，，，

这道最小生成树的题稍微需要处理一下，，不过之后也就是套板子了，，，

题意分析

大致的题意就是给出n个村庄之间的距离，，，然后再给出几个村庄之间已经存在的路径，，，然后让你再添加几条路径使得所有的路径的和最小，，，问你添加的这个值是多少，，，

之前做的那几道题都是图已经弄好，，，路径是给定的问你最小的权重之和，，，这道题相当于给你部分图问你最小的权重和，，，

其实只要在加边建图的时候把给的边的权重置为0当作这条边可以走，但我们不算权重，，这样跑一遍最小生成树就能得到答案，，，

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <string.h>

#include <algorithm>

using namespace std;

const int maxn = 100;

const int maxm = 1e5 + 5;

int mp[maxn][maxn];

int father[maxn];

bool vis[maxn];

int n , m;

int tot;

struct edge

{

    int u , v , w;

    bool operator < (const edge &r) const

    {

        return w < r.w;

    }

}edge[maxm];

void addedge(int _u , int _v , int _w)

{

    edge[tot].u = _u;

    edge[tot].v = _v;

    edge[tot++].w = _w;

}

int find(int x)

{

    if(x == father[x])  return x;

    else return father[x] = find(father[x]);

}

int kruskal()

{

    for(int i = 1; i <= n; ++i)

        father[i] = i;

    sort(edge , edge + tot);

    int cnt = 0;

    int sum = 0;

    for(int i = 1; i < tot; ++i)

    {

        int t1 = find(edge[i].u);

        int t2 = find(edge[i].v);

        if(t1 != t2)

        {

            father[t1] = t2;

            sum += edge[i].w;

            ++cnt;

        }

        if(cnt == n - 1)    break;

    }

    if(n < n - 1)   return -1;

    else            return sum;

}

int main()

{

    while(scanf("%d" , &n) != EOF)

    {

        int u , v , w;

        for(int i = 1; i <= n; ++i)

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

            {

                scanf("%d" , &w);

                addedge(i , j , w);

                addedge(j , i , w);

            }

        scanf("%d" , &m);

        for(int i = 1; i <= m; ++i)

        {

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

            addedge(u , v , 0);

            addedge(v , u , 0);

            //无向图记得正反都要加边，，，少加了一个wa了一发，，，，QAQ

        }

        printf("%d\n" , kruskal());

    }

}

(end)