复习内容
1.spfa
2.背包问题
3.动态规划其他常考问题
4.dfs
5.bfs
6.并查集
一、基础题回顾
1.spfa
问题描述
蒜头君准备去参加骑车比赛，比赛在 n 个城市间进行，编号从 1 到 n。选手们都从城市 1 出发，终点在城市 n。
已知城市间有 m 条道路，每条道路连接两个城市，注意道路是双向的。现在蒜头君知道了他经过每条道路需要花费的时间，他想请你帮他计算一下，他这次比赛最少需要花多少时间完成。
输入格式
第一行输入两个整数\n,m（\1≤n≤1,000,1≤m≤5,000），分别代表城市个数和道路总数。接下来输入 m 行，每行输入三个数字 a,b,c（1≤a,b≤n,1≤c≤200），分别代表道路的起点和道路的终点，以及蒜头君骑车通过这条道路需要花费的时间。保证输入的图是连通的。
输出格式
输出一行，输出一个整数，输出蒜头君完成比赛需要的最少时间。
样例输入
5 6
1 2 2
2 3 3
2 5 5
3 4 2
3 5 1
4 5 1
样例输出
6
题解
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e4+9;
const int M = 1e5+9;
struct edge{
int u;
int w;
int next;
edge(){
}
edge(int uu,int ww,int nn){
u = uu;
w = ww;
next = nn;
}
}e[N << 1];
int head[N],size;
void init(){
memset(head,-1,sizeof(head));
size = 0;
}
void add(int u,int v,int w){
e[size] = edge(u,w,head[v]);
head[v] = size++;
}
void add2(int u,int v,int w){
add(u,v,w);
add(v,u,w);
}
int n,m;
int dis[N];
bool vis[N];
void spfa(int u){
memset(dis,0x3f,sizeof(dis));
dis[u] = 0;
memset(vis,false,sizeof(vis));
vis[u] = true;
queue<int> q;
q.push(u);
while(!q.empty()){
u = q.front();
q.pop();
vis[u] = false;
for(int j = head[u];~j;j = e[j].next){
int v = e[j].u;
int w = e[j].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
if(!vis[v]){
q.push(v);
vis[v] = true;
}
}
}
}
}
int main(){
init();
int u,v,w;
cin >>n>>m;
while(m--){
cin >>u>>v>>w;
add2(u,v,w);
}
spfa(1);
cout <<dis[n]<<endl;
return 0;
}
2.背包问题
01背包
问题描述：
有N件物品和一个容积为M的背包。第i件物品的体积为volume[i]，价值为worth[i]。求解将哪些物品装入背包可使价值总和最大。每种物品只有一件，可以选择放或者不放。（N<=3500,M<=13000）
输入格式：
第一行为物品数量N和背包容积M
每行依次输入第i件物品的价值和体积
样例输入：
3 10
3 4
2 6
6 7
样例输出：
6
#include<iostream>
#include<algorithm>
using namespace std;
int dp[100][100];
int v[100],w[100];
int n,m;
int main(){
cin >>n>>m;
int maxs = -1;
for(int i = 0;i<n;i++){
cin >>v[i]>>w[i];
}
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
if(j < w[i]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
maxs = max(maxs,dp[i][j]);
}
}
cout <<maxs<<endl;
return 0;
}
多重背包
题目描述：
有N种物品，第i种物品的体积是c[i]，价值是w[i]，每种物品的数量都是有限的，为n[i]。现有容量为V的背包，请你放入若干物品，在总体积不超过V的条件下，使总价值尽可能大。
#include<iostream>
#include<cstring>
using namespace std;
int dp[21][1010];
int w[21],c[21],n[21];
int main()
{
int N,V;
cin>>N>>V;
for(int i=1;i<=N;++i)
cin>>w[i]>>c[i]>>n[i];
for(int i=1;i<=N;++i)
{
for(int j=0;j<=V;++j)
{
for(int k=0;k<=n[i];++k)
{
if(j>=c[i]*k)
dp[i][j]=max(dp[i-1][j-c[i]*k]+w[i]*k,dp[i][j]);
}
}
}
cout<<dp[N][V]<<endl;
return 0;
}
完全背包
问题描述：
当前有N种物品，第i种物品的体积是c[i]，价值是w[i]。
每种物品的数量都是无限的，可以任意选择若干件。
现有容量为V的背包，请你放入若干物品，在总体积不超过V的条件下，使总价值尽可能大。
与01背包问题的区别就是物品有无限多个.
#include<iostream>
#include<cstring>
using namespace std;
int dp[21][1010];
int w[21],c[21];
int main()
{
int N,V;
cin>>N>>V;
for(int i=1;i<=N;++i)
cin>>w[i]>>c[i];
for(int i=1;i<=N;++i)
{
for(int j=0;j<=V;++j)
{
if(j>=c[i])
dp[i][j]=max(dp[i][j-c[i]]+w[i],dp[i-1][j]);
else
dp[i][j]=dp[i-1][j];
}
}
cout<<dp[N][V]<<endl;
return 0;
}
3.动态规划其他常考问题
楼梯问题
略
贪心
略
最大字段和
给定N个数A1, A2, ... An，从中选出k（k不固定）个连续的数字 Ai, Ai+1, ... Ai+k-1，使得∑i+k−1iAt 达到最大，求该最大值。
#include<iostream>
#include<algorithm>
using namespace std;
int dp[100];
int a[100];
int n;
int main(){
cin >>n;
int maxs = -1;
for(int i = 1;i<=n;i++){
cin >>a[i];
dp[i] = a[i];
}
for(int i = 2;i<=n;i++){
dp[i] = max(dp[i],dp[i-1]+a[i]);
maxs = max(maxs,dp[i]);
}
cout <<maxs<<endl;
return 0;
}
最长上升子序列
#include<iostream>
#include<algorithm>
using namespace std;
int dp[100];
int a[100];
int n;
int main(){
cin >>n;
int maxs = -1;
for(int i = 1;i<=n;i++){
cin >>a[i];
}
for(int i = 1;i<=n;i++){
dp[i] = 1;
for(int j = 1;j<=i;j++){
if(a[j] < a[i]){
dp[i] = max(dp[i],dp[j]+1);
}
}
maxs = max(maxs,dp[i]);
}
cout <<maxs<<endl;
return 0;
}
数塔问题
在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：
有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
Output
对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。
Sample Input
1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Sample Output
30
#include<iostream>
#include<algorithm>
using namespace std;
int dp[100][100];
int a[100][100];
int n,m;
int main(){
cin >>n>>m;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
cin >>a[i][j];
}
}
for(int i = 0;i<n;i++){
dp[n][i] = a[n][i];
}
for(int i = n-1;i>1;i--){
for(int j = 0;j<=i;j++){
dp[i][j] = max(dp[i+1][j],dp[i+1][j+1])+a[i];
}
}
cout <<dp[0][0]<<endl;
}
4 dfs
问题描述
n个人参加某项特殊考试。
为了公平，要求任何两个认识的人不能分在同一个考场。
求是少需要分几个考场才能满足条件。
输入格式
第一行，一个整数n(1<n<100)，表示参加考试的人数。
第二行，一个整数m，表示接下来有m行数据
以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。
输出格式
一行一个整数，表示最少分几个考场。
样例输入
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
样例输出
4
样例输入
5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
样例输出
5
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e2+2;
int g[MAXN][MAXN];//用邻接矩阵存储关系
int room[MAXN][MAXN]; //room[i][j]表示当前i号教室第j个人为room[i][j]
int MIN ;//优化一：当前状态下的最小教室
int n,m;//点数，边数
void dfs(int v,int c){
if(c>=MIN)return;//剪枝
if(v>n){
MIN=MIN>c?c:MIN;
return;
}
for(int i=1;i<=c;++i){
//循环判断每个教室的每个人是否与v有关系
int k =0;
while(room[i][k]&&g[v][room[i][k]]==0){
//如果当前教室i,第k个人的编号room[i][k]与v有关系退出
k++;
}
if(room[i][k]==0){
//有当前教室i的所有人无关系，可加入教室
room[i][k]=v;
dfs(v+1,c);//把v+1加入到教室
room[i][k]=0;//回溯
}
}
room[c+1][0]=v;//或者新开一间教室放该v,(注不是所有教室不满足条件)
dfs(v+1,c+1);
room[c+1][0]=0;
}
int main(){
//相当于图的着色问题，用dfs
scanf("%d%d",&n,&m);
MIN = n;//易知最多教室为n
int a,b;
for(int i=0;i<m;++i){
scanf("%d%d",&a,&b);
g[a][b]=g[b][a]=1;
}
dfs(1,0);
printf("%d",MIN);
return 0;
}
A - 滑雪 POJ - 1088
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output
25
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int mp[100][100];
int ansm = -1;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int dfs(int x,int y){
int ans = -1;
if(ans > 0){
return ans;
}
ans = 1;
for(int i = 0;i<4;i++){
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(tx >= 0 && tx < n && ty >= 0 && ty < m && mp[tx][ty] < mp[x][y]){
int temp = dfs(tx,ty) + 1;
ans = max(ans,temp);
}
}
return ans;
}
int main(){
cin >>n>>m;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
cin >>mp[i][j];
}
}
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
int t = dfs(i,j);
ansm = max(ansm,t);
}
}
cout <<ansm<<endl;
}
5.bfs
迷宫最短路
#include<iostream>
#include<queue>
using namespace std;
struct node{
int x,y,s;
node(){
}
node(int xx,int yy,int ss){
x = xx;
y = yy;
s = ss;
}
};
int n,m;
char mp[100][100];
bool vis[100][100];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int bfs(int x,int y){
queue<node> q;
q.push(node(x,y,0));
vis[x][y] = true;
while(!q.empty()){
node now = q.front();
q.pop();
for(int i = 0;i<4;i++){
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty] && mp[tx][ty] != '#'){
if(mp[tx][ty] == 'T'){
return now.s + 1;
}else{
vis[tx][ty] = true;
q.push(node(tx,ty,now.s+1));
}
}
}
}
}
int main(){
cin >>n>>m;
for(int i = 0;i<n;i++){
cin >>mp[i];
}
int sx,sy;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
if(mp[i][j] == 'S'){
sx = i;
sy = j;
}
}
}
cout <<bfs(sx,sy)<<endl;
return 0;
}
拓展
dfs与bfs的抽象问题
例1：给定n nn个整数，要求选出K KK个数，使得选出来的K KK个数的和为s u m sumsum
#include <iostream>
using namespace std;
int a[40];
int n, k, sum, ans;
//i表示选择第i个数，cnt记录选择的个数，s表示选取数的和
void dfs(int i, int cnt, int s) {
if (i == n) {
if (cnt == k && s == sum) {
ans++;
}
return;
}
dfs(i + 1, cnt, s); //不选该数
dfs(i + 1, cnt + 1, s + a[i]); //选择该数
}
int main() {
cin >> n >> k >> sum;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
ans = 0;
dfs(0, 0, 0);
cout << ans << endl;
return 0;
}
例2：取木棍：
有4个木棍输入每个木棍长度；
判断是否可以拼成三角形：
比如 1 2 3 3可以拼成三角形：
输出yes；
#include <iostream>
using namespace std;
int n,m,sum;
int a[10010];
bool vis[10010];
bool f;
void dfs(int p,int s,int st)
{
if(f)
{
return ;
}
if(p==3)
{
f=true;
return ;
}
if(s=sum/3)//当前的边正好可以构成三角形的一个边
{
dfs(p+1,0,0);
return ;
}
for(int i=0;i<n;++i)
{
if(!vis[i])
{
vis[i]=true;
dfs(p,s+a[i],i+1);
vis[i]=false;
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;++i)
{
cin>>a[i];
sum+=a[i];
}
if(sum%3!=0)//如果不是3的倍数的话就已经明摆着不可以成功
{
cout<<"no"<<endl;
return 0;
}
else dfs(0,0,0);
if(f) cout<<"yes"<<endl;
else cout<<"no"<<endl;
return 0;
}