学习总结16

# 【模板】最小生成树

## 题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 `orz`。

## 输入格式

第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。

接下来 M 行每行包含三个整数 Xi,Yi,Zi，表示有一条长度为 Zi 的无向边连接结点 Xi,Yi。

## 输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 `orz`。

## 样例 #1

### 样例输入 #1

```
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
```

### 样例输出 #1

```
7
```

## 提示

数据规模：

对于 20% 的数据，N<= 5，M<= 20。

对于 40% 的数据，N<= 50，M<= 2500。

对于 70% 的数据，N<= 500，M<= 10^4。

对于 100% 的数据：1<= N<= 5000，1<= M<= 2* 10^5，1<= Zi <= 10^4。

解题思路

利用prim算法来生成树，但是需要一点优化，如果使用朴素prim有几个数据点会超时，在优化代码中我们只需要用一个数组来保存集合到与集合相邻的点的距离。

朴素代码

#include <bits/stdc++.h>
using namespace std;
int g[6010][6010];
int j[5010];
int g1[5010];
int main()
{
    int x,y,n,m;
    int a,b,c,sum,t,min1,z;
    scanf("%d%d",&n,&m);
    for(x=1;x<=n;x++)
    {
        for(y=1;y<=n;y++)
            g[x][y]=999999;
    }
    for(x=0;x<m;x++)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(c<g[a][b])
            g[a][b]=c;
        if(c<g[b][a])
            g[b][a]=c;
    }
    t=1;
    sum=0;
    g1[1]=1;
    j[1]=1;
    while(t<n)
    {
        min1=99999;
        for(x=1;x<=t;x++)
        {
            y=g1[x];
            for(z=1;z<=n;z++)
            {
                if(min1>g[y][z]&&j[z]!=1)
                {
                    min1=g[y][z];
                    a=y;
                    b=z;
                }
            }
        }
        if(min1==99999)
        {
            printf("orz");
            return 0;
        }
        t++;
        g1[t]=b;
        sum+=g[a][b];
        j[b]=1;
    }
    printf("%d",sum);
    return 0;
}

优化代码

#include <bits/stdc++.h>
using namespace std;
int g[5010][5010];
int j[5010];
int g1[5010];
int ju[5010];
int main()
{
    int x,y,n,m;
    int a,b,c,sum,t,min1,z;
    scanf("%d%d",&n,&m);
    for(x=1;x<=n;x++)
    {
        for(y=1;y<=n;y++)
            g[x][y]=999999;
    }
    for(x=0;x<m;x++)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(c<g[a][b])
            g[a][b]=c;
        if(c<g[b][a])
            g[b][a]=c;
    }
    t=1;
    sum=0;
    g1[1]=1;
    j[1]=1;
    for(x=1;x<=n;x++)
    {
        if(x!=1)
            ju[x]=g[x][1];
    }
    while(t<n)
    {
        min1=99999;
        for(x=1;x<=n;x++)
        {
            if(ju[x]<min1&&j[x]!=1)
            {
                min1=ju[x];
                b=x;
            }
        }
        if(min1==99999)
        {
            printf("orz");
            return 0;
        }
        t++;
        g1[t]=b;
        sum+=min1;
        j[b]=1;
        for(x=1;x<=n;x++)
        {
            if(g[b][x]<ju[x]&&ju[x]!=99999)
                ju[x]=g[b][x];
        }
    }
    printf("%d",sum);
    return 0;
}

# 拆地毯

## 题目背景

还记得 NOIP 2011 提高组 Day1 中的铺地毯吗？时光飞逝，光阴荏苒，三年过去了。组织者精心准备的颁奖典礼早已结束，留下的则是被人们踩过的地毯。请你来解决类似于铺地毯的另一个问题。

## 题目描述

会场上有 n 个关键区域，不同的关键区域由 m 条无向地毯彼此连接。每条地毯可由三个整数 u、v、w 表示，其中 u 和 v 为地毯连接的两个关键区域编号，w 为这条地毯的美丽度。

由于颁奖典礼已经结束，铺过的地毯不得不拆除。为了贯彻勤俭节约的原则，组织者被要求只能保留至多 K 条地毯，且保留的地毯构成的图中，任意可互相到达的两点间只能有一种方式互相到达。换言之，组织者要求新图中不能有环。现在组织者求助你，想请你帮忙算出这至多 K 条地毯的美丽度之和最大为多少。

## 输入格式

第一行包含三个正整数 n、m、K。

接下来 m 行中每行包含三个正整数 u、v、w。

## 输出格式

只包含一个正整数，表示这 K 条地毯的美丽度之和的最大值。

## 样例 #1

### 样例输入 #1

```
5 4 3
1 2 10
1 3 9
2 3 7
4 5 3
```

### 样例输出 #1

```
22
```

## 提示

选择第 1、2、4 条地毯，美丽度之和为 10 + 9 + 3 = 22。

若选择第 1、2、3 条地毯，虽然美丽度之和可以达到 10 + 9 + 7 = 26，但这将导致关键区域 1、2、3 构成一个环，这是题目中不允许的。
1<=n,m,k<=100000

解题思路

只要把所有地毯按照美丽度排序，然后从大到小进行生成树就行了。

代码

#include <bits/stdc++.h>
using namespace std;
int g[100010];
struct ss
{
    int u;
    int v;
    int w;
}j[100010];
int n,m,k;
int u,v,w;
int cmp(ss x,ss y)
{
    return x.w>y.w;
}
int find1(int x)
{
    if(g[x]!=x)
        g[x]=find1(g[x]);
    return g[x];
}
int main()
{
    int x,y,q,e,sum=0;
    scanf("%d%d%d",&n,&m,&k);
    for(x=1;x<=n;x++)
    {
        g[x]=x;
    }
    for(x=1;x<=m;x++)
    {
        scanf("%d%d%d",&j[x].u,&j[x].v,&j[x].w);
    }
    sort(j+1,j+m+1,cmp);
    for(x=1,y=0;x<=m&&y<k;x++)
    {
        q=find1(j[x].u);
        e=find1(j[x].v);
        if(q!=e)
        {
            g[q]=e;
            sum+=j[x].w;
            y++;
        }
    }
    printf("%d",sum);
    return 0;
}