学习总结18

# 营救

## 题目背景

“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……

## 题目描述

妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 t 区，而自己在 s 区。

该市有 m 条大道连接 n 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 s 至 t 的路线，使得经过道路的拥挤度最大值最小。

## 输入格式

第一行有四个用空格隔开的 n，m，s，t，其含义见【题目描述】。

接下来 m 行，每行三个整数 u, v, w，表示有一条大道连接区 u 和区 v，且拥挤度为 w。

**两个区之间可能存在多条大道**。

## 输出格式

输出一行一个整数，代表最大的拥挤度。

## 样例 #1

### 样例输入 #1

```
3 3 1 3
1 2 2
2 3 1
1 3 3
```

### 样例输出 #1

```
2
```

## 提示

#### 数据规模与约定

- 对于 30% 的数据，保证 n<= 10。
- 对于 60% 的数据，保证 n<= 100。
- 对于 100% 的数据，保证 1 <= n<=10^4，1 <= m <= 2 * 10^4，w <= 10^4，1 <= s, t <= n。且从 s 出发一定能到达 t 区。

--- 

#### 样例输入输出 1 解释

小明的妈妈要从 1 号点去 3 号点，最优路线为 1->2->3。

解题思路

简单把所有大道都进行排序，然后按照从小到大的顺序开始生成树，直到起点和终点相同。

代码

#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,q,e,sum=0,s,t;scanf("%d%d%d%d",&n,&m,&s,&t);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;x<=m;x++){q=find1(j[x].u);e=find1(j[x].v);if(q!=e)                                         //根不相同{g[q]=e;                                      //相连if(find1(s)==find1(t))                       //相同，起点和终点互通{printf("%d",j[x].w);break;}}}return 0;
}

# 买礼物

## 题目描述

又到了一年一度的明明生日了，明明想要买 B 样东西，巧的是，这 B 样东西价格都是 A 元。

但是，商店老板说最近有促销活动，也就是：

如果你买了第 I 样东西，再买第 J 样，那么就可以只花 K（I,J） 元，更巧的是，K（I,J） 竟然等于 K（J,I）。

现在明明想知道，他最少要花多少钱。

## 输入格式

第一行两个整数，A,B。

接下来 B 行，每行 B 个数，第 I 行第 J 个为 K（I,J）。

我们保证 K（I,J）=K（J,I） 并且 K（I,I）=0。

特别的，如果 K（I,J）=0，那么表示这两样东西之间不会导致优惠。

注意 K（I,J） **可能大于** A。

## 输出格式

一个整数，为最小要花的钱数。

## 样例 #1

### 样例输入 #1

```
1 1
0
```

### 样例输出 #1

```
1
```

## 样例 #2

### 样例输入 #2

```
3 3
0 2 4
2 0 2
4 2 0
```

### 样例输出 #2

```
7
```

## 提示

样例解释 2。

先买第 2 样东西，花费 3 元，接下来因为优惠，买 1,3 样都只要 2 元，共 7 元。

（同时满足多个“优惠”的时候，聪明的明明当然不会选择用 4 元买剩下那件，而选择用 2 元。）

数据规模

对于 30% 的数据，1<= B<= 10。

对于 100% 的数据，1<= B<=500,0<= A,K(I,J)<=1000。

解题思路

把所有的价格排序，从大到小的进行生成树，这样我们只要把一开始进集合时的几个加上就行了。

代码

#include<bits/stdc++.h>
using namespace std;
int a,b;
struct ss
{int x;int y;int mo;
}g[510*510];
int j[510];
int j2[510];
int find1(int x)
{if(j[x]==x)return x;return j[x]=find1(j[x]);
}
void unit(int x,int y)
{j[find1(y)]=find1(x);
}
int cmp(ss x,ss y)
{return x.mo<y.mo;
}
int main()
{int x,y,n=0,sum;scanf("%d%d",&a,&b);for(x=1;x<=b;x++)j[x]=x;for(x=1;x<=b;x++){for(y=1;y<=b;y++){scanf("%d",&g[++n].mo);if(g[n].mo==0||g[n].mo>a)g[n].mo=a;g[n].x=x;g[n].y=y;}}sort(g+1,g+n+1,cmp);sum=a;for(x=1;x<=n;x++){if(find1(g[x].x)!=find1(g[x].y)){unit(g[x].x,g[x].y);sum+=g[x].mo;}}printf("%d",sum);return 0;
}

# 租用游艇

## 题目描述

长江游艇俱乐部在长江上设置了 n 个游艇出租站 1,2,……,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 r(i,j)（1<= i< j<= n）。试设计一个算法，计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。

## 输入格式

第一行中有一个正整数 n，表示有 n 个游艇出租站。接下来的 n-1 行是一个半矩阵 r(i,j)（1<= i<j<= ）。

## 输出格式

输出计算出的从游艇出租站 1 到游艇出租站 n 所需的最少租金。

## 样例 #1

### 样例输入 #1

```
3
5 15
7
```

### 样例输出 #1

```
12
```

## 提示

n<= 200，保证计算过程中任何时刻数值都不超过 10^6。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int dp[210];
int g[210][210];
int main()
{int x,y;scanf("%d",&n);for(x=1;x<=n-1;x++){for(y=x+1;y<=n;y++){scanf("%d",&g[x][y]);}}for(x=1;x<=n-1;x++){for(y=x;y<=n;y++){if(dp[y]==0||dp[y]>dp[x]+g[x][y]){dp[y]=dp[x]+g[x][y];}}}printf("%d",dp[n]);
}