1.【模板】单源最短路径（弱化版）
2.【模板】单源最短路径（标准版）
3.无线通讯网
4.子串简写
5.整数删除
6.拆地毯
【模板】单源最短路径（标准版）https://www.luogu.com.cn/problem/P4779
题目描述
给定一个 �n 个点，�m 条有向边的带非负权图，请你计算从 �s 出发，到每个点的距离。
数据保证你能从 �s 出发到任意点。
输入格式
第一行为三个正整数 �,�,�n,m,s。 第二行起 �m 行，每行三个非负整数 ��,��,��ui,vi,wi，表示从 ��ui 到 ��vi 有一条权值为 ��wi 的有向边。
输出格式
输出一行 �n 个空格分隔的非负整数，表示 �s 到每个点的距离。
输入输出样例
输入 #1复制
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4输出 #1复制
0 2 4 3
说明/提示
样例解释请参考 数据随机的模板题。
1≤�≤1051≤n≤105；
1≤�≤2×1051≤m≤2×105；
�=1s=1；
1≤��,��≤�1≤ui,vi≤n；
0≤��≤1090≤wi≤109,
0≤∑��≤1090≤∑wi≤109。
【模板】单源最短路径（标准版）https://www.luogu.com.cn/problem/P3371
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数 �,�,�n,m,s，分别表示点的个数、有向边的个数、出发点的编号。
接下来 �m 行每行包含三个整数 �,�,�u,v,w，表示一条 �→�u→v 的，长度为 �w 的边。
输出格式
输出一行 �n 个整数，第 �i 个表示 �s 到第 �i 个点的最短路径，若不能到达则输出 231−1231−1。
输入输出样例
输入 #1复制
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4输出 #1复制
0 2 4 3
说明/提示
【数据范围】
对于 20%20% 的数据：1≤�≤51≤n≤5，1≤�≤151≤m≤15；
对于 40%40% 的数据：1≤�≤1001≤n≤100，1≤�≤1041≤m≤104；
对于 70%70% 的数据：1≤�≤10001≤n≤1000，1≤�≤1051≤m≤105；
对于 100%100% 的数据：1≤�≤1041≤n≤104，1≤�≤5×1051≤m≤5×105，1≤�,�≤�1≤u,v≤n，�≥0w≥0，∑�<231∑w<231，保证数据随机。Update 2022/07/29：两个点之间可能有多条边，敬请注意。
对于真正 100%100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。
样例说明：
图片1到3和1到4的文字位置调换
思路：dijkstra
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int N=2e5+5;
struct edge{
int from;
int to;
int w;
edge(int a,int b,int c){
from=a;
to=b;
w=c;
}
};
vector<edge>e[N];
struct node{
int id;
int n_dis;
node(int a ,int b){
id=a;
n_dis=b;
}
bool operator < (const node& a)const{
return n_dis>a.n_dis;
}
};
int n,m,s,dis[N];
bool done[N];
priority_queue<node>q;
void dijkstra(int s){
for (int i=1;i<=n;++i){
dis[i]=INF;
done[i]=false;
}
dis[s]=0;
q.push(node(s,dis[s]));
while (!q.empty()){
node p=q.top(); q.pop();
if (done[p.id]) continue;
done[p.id]=true;
for (int i=0;i<e[p.id].size();++i){
edge y=e[p.id][i];
if (done[y.to]) continue;
if (dis[y.to] > p.n_dis+y.w){
dis[y.to]=p.n_dis+y.w;
q.push(node(y.to,dis[y.to]));
}
}
}
}
signed main(){
cin>>n>>m>>s;
for (int i=0;i<m;++i){
int u,v,w;
cin>>u>>v>>w;
e[u].push_back(edge(u,v,w));
}
dijkstra(s);
for (int i=1;i<=n;++i){
cout<<dis[i]<<" ";
}
}
无线通讯网https://www.luogu.com.cn/problem/P1991
题目描述
国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络；
每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。
任意两个配备了一条卫星电话线路的哨所（两边都有卫星电话）均可以通话，无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 �D，这是受收发器的功率限制。收发器的功率越高，通话距离 �D 会更远，但同时价格也会更贵。
收发器需要统一购买和安装，所以全部哨所只能选择安装一种型号的收发器。换句话说，每一对哨所之间的通话距离都是同一个 �D。你的任务是确定收发器必须的最小通话距离 �D，使得每一对哨所之间至少有一条通话路径（直接的或者间接的）。
输入格式
第一行，22 个整数 �S 和 �P，�S 表示可安装的卫星电话的哨所数，�P 表示边防哨所的数量。
接下里 �P 行，每行两个整数 �，�x，y 描述一个哨所的平面坐标 (�,�)(x,y)，以 km 为单位。
输出格式
第一行，11 个实数 �D，表示无线电收发器的最小传输距离，精确到小数点后两位。
输入输出样例
输入 #1复制
2 4
0 100
0 300
0 600
150 750输出 #1复制
212.13
说明/提示
数据范围及约定
对于 20%20% 的数据：�=2，�=1P=2，S=1；
对于另外 20%20% 的数据：�=4，�=2P=4，S=2；
对于 100%100% 的数据保证：1≤�≤1001≤S≤100，�<�≤500S<P≤500，0≤�,�≤100000≤x,y≤10000。
思路：Kruskal
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int N=505;
int f[N],s,p;
double dis;
double a[N][2];
struct edge{
int from;
int to;
double w;
};
edge e[N*N];
int find(int x){
if (f[x]==x) return x;
else{
f[x]=find(f[x]);
return f[x];
}
}
bool cmp(const edge& a , const edge& b){
return a.w<b.w;
}
void unionn(int x,int y){
f[find(x)]=find(y);
}
signed main(){
cin>>s>>p;
for (int i=1;i<=p;++i) f[i]=i;
for (int i=1;i<=p;++i){
cin>>a[i][0]>>a[i][1];
}
int bian=0;
for (int i=1;i<=p;++i){
for (int j=i+1;j<=p;++j){
++bian;
e[bian].from=i;
e[bian].to=j;
e[bian].w=sqrt((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]));
}
}
sort(e+1,e+1+bian,cmp);
int cnt=0;
for (int i=1;i<=bian;++i){
if (find(e[i].from) != find(e[i].to)){
unionn(e[i].from,e[i].to);
cnt++;
dis=max(e[i].w,dis);
}
if (cnt==p-s) break;
}
printf("%.2lf",dis);
}拆地毯https://www.luogu.com.cn/problem/P2121
题目描述
会场上有 n 个关键区域，不同的关键区域由 m 条无向地毯彼此连接。每条地毯可由三个整数 u、v、w 表示，其中 u 和 v 为地毯连接的两个关键区域编号，w 为这条地毯的美丽度。
由于颁奖典礼已经结束，铺过的地毯不得不拆除。为了贯彻勤俭节约的原则，组织者被要求只能保留至多 K 条地毯，且保留的地毯构成的图中，任意可互相到达的两点间只能有一种方式互相到达。换言之，组织者要求新图中不能有环。现在组织者求助你，想请你帮忙算出这至多 K 条地毯的美丽度之和最大为多少。
输入格式
第一行包含三个正整数 n、m、K。
接下来 m 行中每行包含三个正整数 u、v、w。
输出格式
只包含一个正整数，表示这 K 条地毯的美丽度之和的最大值。
输入输出样例
输入 #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;
#define int long long
const int N = 1e5+5;
struct edge{
int from;
int to;
int w;
};
edge e[N];
int f[N],n,m,k,cnt,sum;
int find(int x){
if (f[x]==x) return x;
else{
f[x]=find(f[x]);
return f[x];
}
}
void unionn(int i,int j){
f[find(i)]=find(j);
}
bool cmp(const edge& a,const edge& b){
return a.w>b.w;
}
signed main(){
cin>>n>>m>>k;
for (int i=1;i<=n;++i) f[i]=i;
for (int i=1;i<=m;++i){
int u,v,w;
cin>>u>>v>>w;
e[i].from=u;
e[i].to=v;
e[i].w=w;
}
sort(e+1,e+1+m,cmp);
for (int i=1;i<=m;++i){
if (find(e[i].from)!=find(e[i].to)){
unionn(e[i].from,e[i].to);
sum+=e[i].w;
cnt++;
}
if (cnt==k) break;
}
cout<<sum;
}子串简写https://www.dotcpp.com/oj/problem3154.html
题目描述
程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internation-alization 简写成 i18n，Kubernetes （注意连字符不是字符串的一部分）简写成 K8s, Lanqiao 简写成 L5o 等。
在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法（长度小于 K 的字符串不配使用这种简写）。
给定一个字符串 S 和两个字符 c1 和 c2，请你计算 S 有多少个以 c1 开头c2 结尾的子串可以采用这种简写？
输入格式
第一行包含一个整数 K。
第二行包含一个字符串 S 和两个字符 c1 和 c2。
输出格式
一个整数代表答案。
样例输入
复制
4
abababdb a b样例输出
复制
6
提示
符合条件的子串如下所示，中括号内是该子串：
[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]
对于 20% 的数据，2 ≤ K ≤ |S | ≤ 10000。
对于 100% 的数据，2 ≤ K ≤ |S | ≤ 5 × 105。S 只包含小写字母。c1 和 c2 都是小写字母。
|S | 代表字符串 S 的长度。
思路：数据的大小到了10的五次，所以用双重循环肯定会TLE，所以选择优化一下，用一重循环，把前面的可以形成的用计数器记录，然后想后遍历，如果遇到计数器加一，如果遍历到c2，那么就加到总数上
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
string s;
char c1,c2;
int k;
signed main(){
cin>>k;
cin>>s;
cin>>c1>>c2;
int cnt=0,n=0;
for (int i=0;i<s.size();++i){
if (i-k+1>=0 && s[i-k+1]==c1) n++;
if (s[i]==c2) cnt+=n;
}
cout<<cnt;
}
整数删除https://www.dotcpp.com/oj/problem3155.html
题目描述
给定一个长度为 N 的整数数列：A1, A2, . . . , AN。你要重复以下操作 K 次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。输出 K 次操作后的序列。
输入格式
第一行包含两个整数 N 和 K。
第二行包含 N 个整数，A1, A2, A3, . . . , AN。
输出格式
输出 N − K 个整数，中间用一个空格隔开，代表 K 次操作后的序列。
样例输入
复制
5 3
1 4 2 8 7样例输出
复制
17 7
提示
数列变化如下，中括号里的数是当次操作中被选择的数：
[1] 4 2 8 7
5 [2] 8 7
[7] 10 7
17 7
对于 20% 的数据，1 ≤ K < N ≤ 10000。
对于 100% 的数据，1 ≤ K < N ≤ 5 × 105，0 ≤ Ai ≤ 108。
思路：双向链表加上堆优化
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int N=5e5+5;
int v[N], l[N], r[N];
struct node1{
int id;
int w;
node1(int a,int b){
id=a;
w=b;
}
bool operator < (const node1& a)const{
if (w==a.w) return id > a.id;
else return w>a.w;
}
};
priority_queue<node1>q; //存节点的值和下标
int n,k;
void sc(int x){
r[l[x]] = r[x], l[r[x]] = l[x];
v[l[x]] += v[x], v[r[x]] += v[x];
}
signed main(){
cin>>n>>k;
r[0] = 1, l[n + 1] = n;
for (int i=1;i<=n;++i){
cin >> v[i], l[i] = i - 1, r[i] = i + 1, q.push(node1(i, v[i]));
}
while (k--){
node1 p=q.top(); q.pop();
if (p.w!=v[p.id]){
q.push(node1(p.id,v[p.id]));
k++;
}else{
sc(p.id);
}
}
int head = r[0];
while (head != n + 1) {
cout << v[head]<< " ";
head = r[head];
}
}
