2.7学习总结

2.7
1.蓝桥王国（dijkstra）
2.吃奶酪
3.榨取kkksc03
4.补给

蓝桥王国https://www.lanqiao.cn/problems/1122/learning/?page=1&first_category_id=1&name=%E8%93%9D%E6%A1%A5%E7%8E%8B%E5%9B%BD

dijkstra板子题，主要是运用优先队列完成

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
const int INF=0x3f3f3f3f3f3f3f3fLL;
const int N=3e5+5;;
struct edge{
	int from,to,w;
	edge(int a,int b,int c){
		from=a;
		to=b;
		w=c;
	}
}; 		//这个主要是保存图中每个节点的邻居节点
vector<edge>e[N]; 
struct s_node{
	int id,n_dis;	//输入优先队列的成员 
	s_node(int a,int b){
		id=a;
		n_dis=b;
	}
	bool operator < (const s_node & a)const {   //用重载运算符，这个是结构体的写法 
 		return n_dis>a.n_dis;
	}
};
int n,m;
int pre[N];	//主要用于记录前驱节点，帮助记录路径
void print_path(int s,int t) 	//输出从s到t之间的最短路径
{
	if (s==t){
		cout<<0;
		return ;
	}
	print_path(s,pre[t]);
	cout<<t;
}
int dis[N];	//记录每个节点到起点之间的距离 
 
void dijkstra(){
	int s=1;	//起始点s是1 
	bool done[N]; 	//记录是否已经被标记为最短路径 
	for (int i=1;i<=n;++i)	{
		dis[i]=INF;
		done[i]=false;
	}
	dis[s]=0;	//起点到自己的距离是0
	priority_queue<s_node>Q;	//建立优先数组，存储节点信息
	Q.push(s_node(s,dis[s]));	//放第一个节点
	while (!Q.empty()){
		s_node q=Q.top(); Q.pop(); 	//输出第一个节点
		if (done[q.id]) continue;	//如果已经找到了最短路径，那么就没必要继续找了，就直接退出
		done[q.id]=true;
		//开始检查q节点的邻居节点
		for (int i=0;i<e[q.id].size();++i){
			edge y=e[q.id][i];  //表示了q这个节点的第i个邻居节点
			if (done[y.to]) continue;	//如果这个节点已经找到了最短路径，那么就退出
			if (dis[y.to]> y.w+q.n_dis){
				dis[y.to]=y.w+q.n_dis;
				Q.push(s_node(y.to,dis[y.to]));
				pre[y.to]=q.id; 
			}
		} 
	} 
	
}
signed main(){
	cin>>n>>m;
	for (int i=1;i<=n;++i) e[i].clear();
	while (m--){
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back(edge(u,v,w));
	}
	dijkstra();
	for (int i=1;i<=n;++i){
		if (dis[i]>=INF) cout<<-1<<" ";
		else cout<<dis[i]<<" ";
	}
}

榨取kkksc03https://www.luogu.com.cn/problem/P1855

输入格式

第一行三个整数 �,�,�n,M,T，表示一共有 �n（1≤�≤1001≤n≤100）个愿望， kkksc03 的手上还剩 �M（0≤�≤2000≤M≤200）元，他的暑假有 �T（0≤�≤2000≤T≤200）分钟时间。

第 22~�+1n+1 行 ��mi​ , ��ti​ 表示第 �i 个愿望所需要的金钱和时间。

输出格式

一行，一个数，表示 kkksc03 最多可以实现愿望的个数。

思路：01背包问题，就是由两个背包容量

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
const int N=1e5+5;
int dp[205][205],n,m,t,qian[205],tt[205];
signed main() {
	cin>>n>>m>>t;
	for (int i=1;i<=n;++i){
		cin>>qian[i]>>tt[i];
	}
	memset(dp,0,sizeof(dp));
	for (int k=1;k<=n;++k){
		for (int i=m;i>=qian[k];--i){
		for (int j=t;j>=tt[k];--j){
				dp[i][j]=max(dp[i][j],dp[i-qian[k]][j-tt[k]]+1);
			}
	 	}
	}
	cout<<dp[m][t];
}

吃奶酪https://www.luogu.com.cn/problem/P1433

题目描述

房间里放着 �n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0)(0,0) 点处。

输入格式

第一行有一个整数，表示奶酪的数量 �n。

第 22 到第 (�+1)(n+1) 行，每行两个实数，第 (�+1)(i+1) 行的实数分别表示第 �i 块奶酪的横纵坐标 ��,��xi​,yi​。

输出格式

输出一行一个实数，表示要跑的最少距离，保留 22 位小数。

输入输出样例

输入 #1复制

4
1 1
1 -1
-1 1
-1 -1

输出 #1复制

7.41

说明/提示

数据规模与约定

对于全部的测试点，保证 1≤�≤151≤n≤15，∣��∣,∣��∣≤200∣xi​∣,∣yi​∣≤200，小数点后最多有 33 位数字。

提示

对于两个点 (�1,�1)(x1​,y1​)，(�2,�2)(x2​,y2​)，两点之间的距离公式为 (�1−�2)2+(�1−�2)2(x1​−x2​)2+(y1​−y2​)2​。

思路：状态压缩DP

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
const int INF=0x3f3f3f3f3f3f3f3fLL;
#define int long long
double dp[1<<16][20];
double a[20][20];
double x[20],y[20];
int n;
double dis(int i,int j){
	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
signed main(){
	cin>>n;
	memset(dp,127,sizeof(dp));
	for (int i=1;i<=n;++i){	
			cin>>x[i]>>y[i];
			dp[1<<(i-1)][i]=dis(i,0);
	}
	x[0]=0,y[0]=0;
	for (int i=0;i<n;++i){
		for (int j=i+1;j<=n;++j){
			a[i][j]=dis(i,j);
			a[j][i]=a[i][j];
		}
	}
	for (int s=1;s<(1<<n);++s){
		for (int i=1;i<=n;++i){
			if ((s&(1<<(i-1)))==0) continue;
			//if (s==(1<<(i-1))) dp[s][i]=dis(i,0);
			for (int j=1;j<=n;++j){
				if (i==j) continue;
				if ((s&(1<<(j-1)))==0) continue;
				dp[s][i]=min(dp[s][i],dp[s^(1<<(i-1))][j]+a[i][j]); 
			}
		}
	}
	double ans=100000000.0;
	for (int i=1;i<=n;++i){
		ans=min(ans,dp[(1<<n)-1][i]);
	}
	printf("%.2lf\n",ans);
}

补给https://www.luogu.com.cn/problem/solution/P8733

题目描述

小蓝是一个直升飞机驾驶员，他负责给山区的 �n 个村庄运送物资。

每个月，他都要到每个村庄至少一次，可以多于一次，将村庄需要的物资运送过去。

每个村庄都正好有一个直升机场，每两个村庄之间的路程都正好是村庄之间的直线距离。

由于直升机的油箱大小有限，小蓝单次飞行的距离不能超过 �D。每个直升机场都有加油站，可以给直升机加满油。

每个月，小蓝都是从总部出发，给各个村庄运送完物资后回到总部。如果方便，小蓝中途也可以经过总部来加油。

总部位于编号为 11 的村庄。

请问，要完成一个月的任务，小蓝至少要飞行多长距离？

输入格式

输入的第一行包含两个整数 �n，�D，分别表示村庄的数量和单次飞行的距离。

接下来 �n 行描述村庄的位置，其中第 �i 行两个整数 ��xi​，��yi​ 分别表示编号为 �i 的村庄的坐标。村庄 �i 和村庄 �j 之间的距离为 (��−��)2+(��−��)2(xi​−xj​)2+(yi​−yj​)2​。

输出格式

输出一行，包含一个实数，四舍五入保留正好 22 位小数，表示答案。

输入输出样例

输入 #1复制

4 6
1 1
4 5
8 5
11 1

输出 #1复制

28.00

说明/提示

对于所有数据，保证，1≤�≤20,1≤��,��≤104,1≤�≤1051≤n≤20,1≤xi​,yi​≤104,1≤D≤105。

思路：floyd找到最短路径，然后状压DP

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
const int N=1e5+5;
double dp[1<<20][25],a[25][25];
int n,d;
double x[21],y[21];
double dis(int i,int j){
	return sqrt(((x[i]-x[j])*(x[i]-x[j]))+((y[i]-y[j])*(y[i]-y[j])));
}
void floyd(){
	for (int k=1;k<=n;++k){
		for (int i=1;i<=n;++i){
			for (int j=1;j<=n;++j){
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
			}
		}
	}
}
signed main() {
	cin>>n>>d;
	for (int i=1;i<=n;++i){
		cin>>x[i]>>y[i];
	}
	for (int i=1;i<=n;++i){
		for (int j=1;j<=n;++j){
			if (dis(i,j)>d){
				a[i][j]=1e10;
			}
			else {
				a[i][j]=dis(i,j);
			}
		}
	}
	floyd();
	for(int i=0;i<(1<<n);++i){
		for(int j=1;j<=n;++j){
			dp[i][j]=1e10;
		}
	}
	dp[1][1]=0;
	for (int s=0;s<(1<<n);++s){
		for (int j=1;j<=n;++j){
			if ((s&(1<<(j-1)))==0) continue;
			for (int k=1;k<=n;++k){
				if (j==k)continue;
				if ((s&(1<<(k-1)))==0) continue;
				dp[s][j]=min(dp[s][j],dp[s^(1<<(j-1))][k]+a[k][j]);
			}
		}
	}
	double res=1e13;
	for (int i=1;i<=n;++i){
		res=min(res,dp[(1<<n)-1][i]+a[i][1]);
	}
	printf("%.2lf",res);
}