信息学奥赛-提高级 题库
一个包含8个顶点的完全图(顶点编号1到8),任意两点之间的边权重等于两顶点编号的差的绝对值,该图的最小生成树总权重是多少?
最小生成树是选边构成树且权值和最小。用Kruskal算法,将边权从小到大排序,边权最小的边为(1,2)、(2,3)、(3,4)、(4,5)、(5,6)、(6,7)、(7,8),权值均为1,总和7。
有如下的有向图,节点为 A, B, … , J, 其中每条边的长度都标在图中。则节点 A 到节点 J 的最短路径长度为( )。

有如下的有向图,节点为 A, B, … , J, 其中每条边的长度都标在图中。则节点 A 到节点 J 的最短路径长度为( )。

特殊最短路
题目背景
给定一个含N个点、M条边的带权无向图,边权非负。起点为S,终点为T。对于一条S到T的路径,可以在整条路径中,至多选择一条边作为“免费边”:当第一次经过这条被选中的边时,费用视为0;如果之后再次经过该边,则仍按其原始权重视计费。点和边均允许重复经过。求从S到T的最小总费用。
以下代码求解了上述问题。试补全程序。
(交通中断)有一个小国家,国家内有n座城市和m条双向的道路,每条道路连接着两座不同的城市。其中1号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道,如果只有第i(i>1)个城市因地震而
导致交通中断时,首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第i个城市而导致从首都出发无法到达某个城市,也认为到达该城市的最短路径长度改变。
对于每一个城市i,假定只有第i个城市与外界交通中断,输出有多少个城市会因此导致到首都的最短路径长度改变。
我们采用邻接表的方式存储图的信息,其中head[x]表示顶点x的第一条边的编号,next[i]表示第i条边的下一条边的编号,point[i]表示第i条边的终点,weight[i]表示第i条边的长度。(第一空2分,其余3分)
#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 6000
#define MAXM 100000
#define infinity 2147483647
int head[MAXN], next[MAXM], point[MAXM], weight[MAXM];
int queue[MAXN], dist[MAXN], visit[MAXN];
int n, m, x, y, z, total = 0, answer;
void link(int x,int y,int z) {
total++;
next[total] = head[x];
head[x] = total;
point[total] = y;
weight[total] = z;
total++;
next[total] = head[y];
head[y] = total;
point[total] = x;
weight[total] = z;
}
int main() {
int i, j, s, t;
cin >> n >> m;
for (i = 1; i <= m; i++) {
cin >> x >> y >> z; link(x, y, z);
}
for (i = 1; i <= n; i++) dist[i] = infinity;
(1) ;
queue[1] = 1;
visit[1] = 1;
s = 1;
t = 1;
// 使用 SPFA 求出第一个点到其余各点的最短路长度
while (s <= t) {
x = queue[s % MAXN];
j = head[x];
while (j != 0) {
if ( (2) ) {
dist[point[j]] = dist[x] + weight[j];
if (visit[point[j]] == 0) {
t++;
queue[t % MAXN] = point[j];
visit[point[j]] = 1;
}
}
j = next[j];
}
(3) ;
s++;
}
for (i = 2; i <= n; i++) {
queue[1] = 1;
memset(visit, 0, sizeof(visit));
visit[1] = 1;
s = 1;
t = 1;
while (s <= t) { // 判断最短路长度是否不变
x = queue[s];
j = head[x];
while (j != 0) {
if (point[j] != i && (4)
&&visit[point[j]] == 0) {
(5) ;
t++;
queue[t] = point[j];
}
j = next[j];
}
s++;
}
answer = 0;
for (j = 1; j <= n; j++)
answer += 1 - visit[j];
cout << i << ":" << answer - 1 << endl;
}return 0;
}
(1)dist[1]=0
(2) dist[x]+weight[j]<dist[point[j]]
(3)visit[x]=0
(4)dist[x]+weight[j]==dist[point[j]]
(5)visit[point[j]]=1
(最短路径问题)无向连通图G有n个结点,依次编号为0,1,2,...,(n-1)。用邻接矩阵的形式给出每条边的边长,要求输出以结点0为起点出发,到各结点的最短路径长度。
使用Dijkstra算法解决该问题:利用dist数组记录当前各结点与起点的已找到的最短路径长度;每次从未扩展的结点中选取dist值最小的结点v进行扩展,更新与v相邻的结点的dist值;不断进行上述操作直至所有结点均被扩展,此时dist数据中记录的值即为各结点与起点的最短路径长度。(第五空 2 分,其余 3 分)
#include <iostream>
using namespace std;
const int MAXV = 100;
int n, i, j, v;
int w[MAXV][MAXV]; // 邻接矩阵,记录边长
// 其中 w[i][j]为连接结点 i 和结点 j 的无向边长度,若无边则为-1
int dist[MAXV];
int used[MAXV]; // 记录结点是否已扩展(0:未扩展;1:已扩展)
int main() {
cin >> n;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
cin >> w[i][j];
dist[0] = 0;
for (i = 1; i < n; i++)
dist[i] = -1;
for (i = 0; i < n; i++)
used[i] = 0;
while (true) {
(1) ;
for (i = 0; i < n; i++)
if (used[i] != 1 && dist[i] != -1 && (v == -1 || (2) ))
(3) ;
if (v == -1)
break;
(4) ;
for (i = 0; i < n; i++)
if (w[v][i] != -1 && (dist[i] == -1 || (5) ))
dist[i] = dist[v] + w[v][i];
}
for (i = 0; i < n; i++)
cout << dist[i] << endl;
return 0;
}
(1)v=-1
(2)dist[i]<dist[v] 或 dist[v]>dist[i] 或 dist[i]<=dist[v] 或 dist[v]>=dist[i]
(3)v=i
(4)used[v]=1
(5)dist[v]+w[v][i]<dist[i] 或 dist[i]>dist[v]+w[v][i] 或 dist[v]+w[v][i]<=dist[i] 或 dist[i]>=dist[v]+w[v][i]
已知带权有向图 G 上的所有权值均为正整数,记顶点 u 到顶点 v 的最短路径的权值为d(u, v)。若 v1, v2, v3, v4, v5是图 G 上的顶点,且它们之间两两都存在路径可达,则以下说法正确的有( )。
对右图使用Dijkstra算法计算S点到其余各点的最短路径长度时,到B点的距离d[B]初始时赋为8,在算法的执行过程中还会出现的值有( )。

逛公园
【问题描述】
策策同学特别喜欢逛公园。公园可以看成一张N个点M条边构成的有向图,且没有自环和重边。其中1号点是公园的入口,N号点是公园的出口,每条边有一个非负权值,代表策策经过这条边所要花的时间。
策策每天都会去逛公园,他总是从1号点进去,从N号点出来。
策策喜欢新鲜的事物,他不希望有两天逛公园的路线完全一样,同时策策还是一个特别热爱学习的好孩子,他不希望每天在逛公园这件事上花费太多的时间。如果1号点到N号点的最短路长为d,那么策策只会喜欢长度不超过d+ K的路线。
策策同学想知道总共有多少条满足条件的路线,你能帮帮他吗?
为避免输出过大,答案对P取模。
如果有无穷多条合法的路线,请输出−1。
【输入格式】
输入文件名为 park.in。
第一行包含一个整数 T, 代表数据组数。
接下来M行,每行三个整数ai, bi, ci,代表编号为ai, bi的点之间有一条权值为 ci的有向边,每两个整数之间用一个空格隔开。
【输出格式】
输出文件名为 park.out。
输出文件包含 T行,每行一个整数代表答案。
【输入输出样例 1】

对于第一组数据,最短路为 3。
1 – 5, 1 – 2 – 4 – 5, 1 – 2 – 3 – 5 为 3 条合法路径。
【数据规模与约定】
对于不同的测试点,我们约定各种参数的规模不会超过如下

对于 100%的数据, 1 ≤ p ≤ 10^9,1 ≤ ai, bi ≤ N , 0 ≤ ci ≤ 1000。
数据保证:至少存在一条合法的路线。
#include <bits/stdc++.h>
using namespace std;
const int Maxn=100010;
const int Maxm=200010;
int t,n,m,size,k,mod,ans,minn,flag;
int dis[Maxn],First[Maxn],first[Maxn],f[Maxn][55],vis[Maxn][55];
struct shu{int to,next,len;};
shu Edge[Maxm],edge[Maxm];
priority_queue<pair<int,int> >q;
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='-') {f=-1;c=getchar();}
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline void clean()
{
size=ans=flag=0;
memset(dis,0x3f3f3f,sizeof(dis));
memset(First,0,sizeof(First));
memset(first,0,sizeof(first));
memset(f,-1,sizeof(f));
memset(vis,0,sizeof(vis));
}
inline void build(int x,int y,int z)
{
Edge[++size].next=First[x];
First[x]=size;
Edge[size].to=y,Edge[size].len=z;
edge[size].next=first[y];
first[y]=size;
edge[size].to=x,edge[size].len=z;
}
inline void dijkstra()
{
q.push(make_pair(0,1)),dis[1]=0;
while(!q.empty())
{
int point=q.top().second;
q.pop();
for(int u=First[point];u;u=Edge[u].next)
{
int to=Edge[u].to;
if(dis[to] > dis[point] + Edge[u].len)
{
dis[to]=dis[point] + Edge[u].len;
q.push(make_pair(-dis[to],to));
}
}
}
}
inline int dfs(int point,int k)
{
if(~f[point][k]) return f[point][k];
f[point][k]=0,vis[point][k]=1;
for(register int u=first[point];u;u=edge[u].next)
{
int to=edge[u].to,num=dis[point]-dis[to]+k-edge[u].len;
if(num<0) continue;
if(vis[to][num]) flag=1;
f[point][k]=(f[point][k]+dfs(to,num))%mod;
}
vis[point][k]=0;
return f[point][k];
}
int main()
{
t=get_int();
while(t--)
{
clean();
n=get_int(),m=get_int(),k=get_int(),mod=get_int();
for(int i=1;i<=m;i++)
{
int x=get_int(),y=get_int(),z=get_int();
build(x,y,z);
}
dijkstra();
if(!dis[n]) {cout<<"-1\n";continue;}
f[1][0]=1;
for(int i=0;i<=k;i++) ans=(ans+dfs(n,i))%mod;
if(!flag) cout<<ans<<"\n";
else cout<<"-1\n";
}
return 0;
}
寻找道路
【问题描述】
在有向图 G 中,每条边的长度均为 1,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件:
1.路径上的所有点的出边所指向的点都直接或间接与终点连通。
2.在满足条件 1 的情况下使路径最短。
注意:图 G 中可能存在重边和自环,题目保证终点没有出边。
请你输出符合条件的路径的长度。
【输入】
输入文件名为 road.in。
第一行有两个用一个空格隔开的整数 n 和 m,表示图有 n 个点和 m 条边。
接下来的 m 行每行 2 个整数 x、y,之间用一个空格隔开,表示有一条边从点 x 指向点y。
最后一行有两个用一个空格隔开的整数 s、t,表示起点为 s,终点为 t。
【输出】
输出文件名为 road.out。
输出只有一行,包含一个整数,表示满足题目᧿述的最短路径的长度。如果这样的路径不存在,输出-1。
【输入输出样例 1】

【输入输出样例说明】

如上图所示,箭头表示有向道路,圆点表示城市。起点 1 与终点 3 不连通,所以满足题目描述的路径不存在,故输出-1。
【输入输出样例 2】

【输入输出样例说明】

如上图所示,满足条件的路径为 1->3->4->5。注意点 2 不能在答案路径中,因为点 2连了一条边到点 6,而点 6 不与终点 5 连通。
【数据说明】

#include<bits/stdc++.h>
#define ll long long
#define MAXN 500010
#define N 201
#define INF 0x7f7f7f7f
#define gtc() getchar()
using namespace std;
template <class T>
inline void read(T &s){
s = 0; T w = 1, ch = gtc();
while(!isdigit(ch)){if(ch == '-') w = -1; ch = gtc();}
while(isdigit(ch)){s = s * 10 + ch - '0'; ch = gtc();}
s *= w;
}
template <class T>
inline void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x/10);
putchar(x % 10 + '0');
}
struct node{
int y, ne, z;
}e[MAXN];
int lin[MAXN], len = 0;
inline void add(int x, int y, int z){
e[++len].y = y, e[len].ne = lin[x], lin[x] = len;
e[len].z = z;
}
int n, m;
int st, ed;
int col[MAXN], vis[MAXN];
void bfs(int u){
queue<int> q;
q.push(u);
vis[u] = 1;
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = lin[x]; i; i = e[i].ne){
int y = e[i].y;
if(e[i].z == 1) continue;
if(vis[y]) continue;
vis[y] = 1;
q.push(y);
}
}
}
void bfs2(int u){//这个不是bfs,之前写错写成bfs,后来直接在这个函数里改了。
col[u] = 1;
for(int i = lin[u]; i; i = e[i].ne){
int y = e[i].y;
if(e[i].z == 1) continue;
if(col[y]) continue;
col[y] = 1;
q.push(y);
}
}
int dis[MAXN];
void bfs3(int u){
memset(dis, INF, sizeof(dis));
dis[u] = 0;
queue<int> q;
q.push(u);
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = lin[x]; i; i = e[i].ne){
int y = e[i].y;
if(e[i].z == 2) continue;
if(col[y]) continue;
if(dis[y] != INF) continue;
dis[y] = dis[x] + 1;
q.push(y);
}
}
}
int main()
{
read(n), read(m);
int x, y;
for(int i = 1; i <= m; ++i){
read(x), read(y);
add(x, y, 1); add(y, x, 2);//1为正边,2为负边
}
read(st), read(ed);
bfs(ed);
for(int i = 1; i <= n; ++i){
if(!vis[i]){
bfs2(i);
}
}
bfs3(st);
if(dis[ed] == INF) puts("-1");
else printf("%d\n", dis[ed]);
return 0;
}