首页 › 题库 › 信息学奥赛 › 4 图论算法

信息学奥赛-提高级 题库

共 13 道题 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 4.1 最小生成树

一个包含8个顶点的完全图(顶点编号1到8),任意两点之间的边权重等于两顶点编号的差的绝对值,该图的最小生成树总权重是多少?

A
7
B
8
C
9
D
10
答案与解析
正确答案:A

最小生成树是选边构成树且权值和最小。用Kruskal算法,将边权从小到大排序,边权最小的边为(1,2)、(2,3)、(3,4)、(4,5)、(5,6)、(6,7)、(7,8),权值均为1,总和7。

题目详情
2 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

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

A
16
B
19
C
20
D
22
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
3 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 4.1 最小生成树

6 个顶点的连通图的最小生成树,其边数为( )。

A
6
B
5
C
7
D
4
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
4 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

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

A
16
B
19
C
20
D
22
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
5 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

特殊最短路

题目背景

给定一个含N个点、M条边的带权无向图,边权非负。起点为S,终点为T。对于一条S到T的路径,可以在整条路径中,至多选择一条边作为“免费边”:当第一次经过这条被选中的边时,费用视为0;如果之后再次经过该边,则仍按其原始权重视计费。点和边均允许重复经过。求从S到T的最小总费用。

以下代码求解了上述问题。试补全程序。

include <algorithm>
include <iostream>
include <queue>
include <vector>
using namespace std;
const long long INF = 1e18;
struct Edge {
    int to;
    int weight;
};
struct State {
    long long dist;
    int u;
    int used_freebie; // 0 for not used, 1 for used
    bool operator>(const State &other) const {
        return dist > other.dist;
    }
};
int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    vector<vector<Edge>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    vector<vector<long long>> d(n + 1, vector<long long>(2, INF));
    priority_queue<State, vector<State>, greater<State>> pq;
    d[s][0] = 0;
    pq.push(    ①   ); // ①处待完善(注:原文①处对应初始化相关)
    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();
        long long dist = current.dist;
        int u = current.u;
        int used = current.used_freebie;
        if (dist >    ②     ) { // ②处待完善
            continue;
        }
        for (const auto &edge : adj[u]) {
            int v = edge.to;
            int w = edge.weight;
            // 情况1:不使用免费边
            if (d[v][used] >    ③    + w) { // ③处待完善
                d[v][used] = d[u][used] + w;
                pq.push({d[v][used], v, used});
            }
            // 情况2:使用免费边(仅当未使用过)
            if (used == 0 && d[v][1] >    ④     + 0) { // ④处待完善
                d[v][1] = d[u][0] + 0;
                pq.push({d[v][1], v, 1});
            }
        }
    }
    cout <<     ⑤    << endl; // ⑤处待完善
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
6 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

下列关于最短路算法的说法正确的有( )。(2018年提高组)

答案与解析
正确答案:A,B,D
这道题暂未补解析。
题目详情
7 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

 (交通中断)有一个小国家,国家内有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

题目详情
8 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

(最短路径问题)无向连通图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]

题目详情
9 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

已知带权有向图 G 上的所有权值均为正整数,记顶点 u 到顶点 v 的最短路径的权值为d(u, v)。若 v1, v2, v3, v4, v5是图 G 上的顶点,且它们之间两两都存在路径可达,则以下说法正确的有(  )。

答案与解析
正确答案:C,D
这道题暂未补解析。
题目详情
10 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

对右图使用Dijkstra算法计算S点到其余各点的最短路径长度时,到B点的距离d[B]初始时赋为8,在算法的执行过程中还会出现的值有( )。

答案与解析
正确答案:B,C,D
这道题暂未补解析。
题目详情
11 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

下列关于最短路算法的说法正确的有( )。

答案与解析
正确答案:A,B,D
这道题暂未补解析。
题目详情
12 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

逛公园

【问题描述】

策策同学特别喜欢逛公园。公园可以看成一张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;

}

题目详情
13 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

寻找道路

【问题描述】

在有向图 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;

}

题目详情