最大子序列和
https://www.acwing.com/problem/content/description/1481/
#include<iostream>
using namespace std;
const int N=100010;
int n;
int a[N];
int main()
{
scanf("%d",&n);
bool flag=false;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(a[i]>=0) flag=true;
}
if(!flag)
{
printf("0 %d %d",a[0],a[n-1]);
return 0;
}
int res=-0x3f3f3f3f;
int first,last;
for(int i=0;i<n;i++)
{
int sum=0;
for(int j=i;j<n;j++)
{
sum+=a[j];
if(sum>res)
{
res=sum;
first=i;
last=j;
}
}
}
printf("%d %d %d",res,a[first],a[last]);
}
7-5 堆中的路径
将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。
输入格式:
每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。
输出格式:
对输入中给出的每个下标i，在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。
输入样例:
5 3
46 23 26 24 10
5 4 3
输出样例:
24 23 10
46 23 10
26 10
#include<iostream>
#include<algorithm>
using namespace std;
int a[100010];
void up(int u)
{
while(u/2 && a[u/2]>a[u])
{
swap(a[u],a[u/2]);
u/=2;
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
up(i);
}
for(int i=1;i<=n;i++) printf("%d ",a[i]);
cout<<endl;
while(m--)
{
int x;
scanf("%d",&x);
while(x)
{
if(x!=1)
printf("%d ",a[x]);
else printf("%d",a[x]);
x/=2;
}
printf("\n");
}
}
7-9旅游规划
https://pintia.cn/problem-sets/15/problems/717
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入格式:
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。
输出格式:
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
输入样例:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
输出样例:
3 40
dijkstra
注意当dist[j]>dist[t]+g[t][j]时，过路费一定要取路程最短的过路费而不是过路费的最小值。
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510;
int g[N][N],dist[N],mo[N],mon[N][N];
bool st[N];
int n,m,s,d;
int dijkstra()
{
memset(dist,0x3f,sizeof dist);
memset(mo,0x3f,sizeof mo);
dist[s]=0;
mo[s]=0;
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=0;j<n;j++)
{
if(!st[j]&&(t==-1||dist[t]>dist[j]||dist[t]==dist[j]&&mo[t]>mo[j]))
t=j;
}
st[t]=true;
for(int j=0;j<n;j++)
{
if(dist[j]>dist[t]+g[t][j])
{
dist[j]=min(dist[j],dist[t]+g[t][j]);
mo[j]=mo[t]+mon[t][j];
}
else if(dist[j]==dist[t]+g[t][j]&&mo[j]>mo[t]+mon[t][j])
{
dist[j]=min(dist[j],dist[t]+g[t][j]);
mo[j]=mo[t]+mon[t][j];
}
}
}
return dist[d];
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&d);
memset(g,0x3f,sizeof g);
memset(mon,0x3f,sizeof mon);
while(m--)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
g[a][b]=g[b][a]=c;
mon[a][b]=mon[b][a]=d;
}
dijkstra();
cout<<dist[d]<<" "<<mo[d]<<endl;
}
Floyd
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510;
int g[N][N][2];//g[i][j][0]表示i，j两点间的距离,g[i][j][1]表示收费
int n,m,s,d;
void floyd()
{
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(g[i][j][0]>g[i][k][0]+g[k][j][0])
{
g[i][j][0]=g[i][k][0]+g[k][j][0];
g[i][j][1]=g[i][k][1]+g[k][j][1];
}
else if(g[i][j][0]==g[i][k][0]+g[k][j][0])
g[i][j][1]=min(g[i][j][1],g[i][k][1]+g[k][j][1]);
}
}
}
cout<<g[s][d][0]<<" "<<g[s][d][1]<<endl;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&d);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j){
g[i][j][0]=g[j][i][0]=0;//注意是无向图
g[i][j][1]=g[j][i][1]=0;
}
else{
g[i][j][0]=g[j][i][0]=0x3f3f3f3f;
g[i][j][1]=g[j][i][1]=0x3f3f3f3f;
}
}
}
while(m--)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
g[a][b][0]=g[b][a][0]=min(g[a][b][0],c);
g[a][b][1]=g[b][a][1]=min(g[a][b][1],d);
}
floyd();
}
7-10 公路村村通 (30 分)
现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。
输入样例:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
输出样例:
12
kruskal模板
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3010;
struct E{
int a,b,c;
}e[N];
int n,m;
int p[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
bool cmp(E a,E b)
{
return a.c<b.c;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++) p[i]=i;
for(int i=0;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[i]={a,b,c};
}
sort(e,e+m,cmp);
int res=0,cnt=0;
for(int i=0;i<m;i++)
{
int a=e[i].a,b=e[i].b;
a=find(a);
b=find(b);
if(a!=b)
{
p[a]=b;
res+=e[i].c;
cnt++;
}
}
if(cnt<n-1) printf("-1");
else printf("%d",res);
}
