这里是记录所有学过的模板的（好像还不会背啊）
Floyd
link
给出一张由 $n$ 个点 $m$ 条边组成的无向图。
求出所有点对 $(i,j)$ 之间的最短路径。
输入 #1
1
2
3
4
5
| 4 4
1 2 1
2 3 1
3 4 1
4 1 1
|
输出 #1
1
2
3
4
| 0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0
|
对于 $100%$ 的数据，$n \le 100$，$m \le 4500$，任意一条边的权值 $w$ 是正整数且 $1 \leqslant w \leqslant 1000$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include <bits/stdc++.h>
using namespace std;
int n,m,dis[110][110];
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
int main()
{
scanf("%d%d",&n,&m);
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
dis[u][v]=dis[v][u]=min(dis[u][v],w);
}
for(int i=1;i<=n;i++)dis[i][i]=0;
floyd();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)printf("%d ",dis[i][j]);
puts("");
}
return 0;
}
|
缩点
link
给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
输入 #1
输出 #1
ST 表 & RMQ 问题
link
给定一个长度为 $N$ 的数列，和 $ M $ 次询问，求出每一次询问的区间内数字的最大值。
输入 #1
1
2
3
4
5
6
7
8
9
10
| 8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8
|
输出 #1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <bits/stdc++.h>
using namespace std;
int lg[100010],f[100010][30],n,m;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int main()
{
n=read(),m=read();
lg[1]=0;
for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
for(int i=1;i<=n;i++)
f[i][0]=read();
for(int j=1;j<=lg[n];j++)
for(int i=1;i<=n-(1<<j)+1;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
for(int i=1;i<=m;i++)
{
int l=read(),r=read(),k=lg[r-l+1];
printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k]));
}
return 0;
}
|