7.26图论基础专项训练题解

发表于 | 分类于 ， | 热度 ℃
字数统计: 6,017 | 阅读时长 ≈ 29

问题 A: 签到题之青蛙爬楼梯

时间限制: 1 Sec 内存限制: 128 MB
提交: 117 解决: 37
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

楼梯有n阶台阶，青蛙每次可以跳1~n阶台阶，问青蛙共有多少种上楼梯的方法。

输入

输入仅一行，一个整数n（n<=50）

输出

输出n阶台阶对应上楼梯的方法。

样例输入

1
3

样例输出

1
4

提示

本题作为水题，不作为图论题。样例提示（1，1，1），（1，2），（2，1），（3）共4种方法

题解

第n阶台阶，我们可以从n-1跳到n，可以从n-2跳到n……可以从1跳到n，也可以从0跳到n。那么要求第n阶的数量，只需求前n-1阶，前n-2阶……前1阶的方法，所以我们列出关系式为F(n)=F(n-1)+F(n-2)+……+F(1)+1。同理，第n-1阶的关系式为F(n-2)+F(n-3)+……+F(1)+1。两个式子合并得F(n)=2*F(n-1)。由于F(1)=1,所以F(n)=2^(n-1)。

代码参考

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int n;
    cin>>n;
    ll a = pow(2,n-1);
    cout<<a<<endl;
    return 0;
}

问题 B: 排名

时间限制: 1 Sec 内存限制: 128 MB
提交: 60 解决: 24
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

有 N 个比赛队（1<=N<=500），编号依次为 1，2，3……N 进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即 P1 赢 P2，用 P1，P2 表示，排名时 P1 在 P2之前。现在请你编程序确定排名。

符合条件的排名可能不是唯一的。此时要求输出时编号小的队伍在前。输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

输入

输入有若干组。每组中的第一行为二个数N（1<=N<=500）。M；当中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中。每行也有两个整数P1。P2表示即P1队赢了P2队。

输出

给出一个符合要求的排名。输出时队伍号之间有空格。最后一名后面没有空格。

样例输入

1
2
3
4
4 3
1 4
4 3
2 3

样例输出

1
1 2 4 3

题解

拓扑排序模板题，唯一可能出现问题的地方就是题目要求同样拓扑序的两个编号小的要在前面，这点可以通过将普通拓扑排序中的队列改为使用优先队列或者堆来实现。

代码参考

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int maxn=510;
int graph[maxn][maxn];//保存图
int degree[maxn];//保存入度

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(graph,0,sizeof(graph));
        memset(degree,0,sizeof(degree));
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            if(!graph[u][v])
            {
                graph[u][v]=1;
                degree[v]++;//的入度++
            }
        }
        priority_queue<int,vector<int>,greater<int> >q;
        for(int i=1;i<=n;i++)
            if(degree[i]==0)
            q.push(i);
        bool first=1;
        while(!q.empty())
        {
            int cur=q.top();
            q.pop();
            if(first)
            {
                cout<<cur;
                first=0;
            }
            else
                cout<<" "<<cur;
            for(int i=1;i<=n;i++)
            {
                if(graph[cur][i]==1)
                {
                    degree[i]--;//相连的点的入度减1
                    if(degree[i]==0)//假设入度为0，增加队列
                        q.push(i);
                }
            }
        }
        printf("\n");
    }
    return 0;
}

问题 C: 系兄弟就来砍我

时间限制: 1 Sec 内存限制: 128 MB
提交: 34 解决: 10
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

渣渣灰因为一句“大家好，我系渣渣辉，系兄弟就来砍我”引得众粉丝纷纷拿两米长的大刀寻找。现有n个据点，编号（1~n），有m条单向路使据点相连。每个据点仅有一个人。这n个人中有k个粉丝。其中渣渣灰在s据点处。请问这k个粉丝到渣渣灰的最短距离是多少

输入

首行输入nmks。(k<=n<=100m<=500)s为渣渣灰所在位置

接下来m行，每行输入xyz，表示从x到y的距离是z，由于是单向边，则y到x的距离不一定是z。

接下来k个数字，表示粉丝所在据点。

输出

对于每一个粉丝，输出对应的最短距离。

样例输入

1
2
3
4
5
3 3 2 1
1 2 1
2 3 1
3 1 1
2 3

样例输出

1
2 1

提示

数据保证k个粉丝均能到达渣渣灰的据点

题解

首先，既然要求k个点到s点的最短路，我们可以反过来求s到这k个点的最短路。这样就变成了单源最短路问题，dijkstra算法和spfa算法都可以做。由于图为有向图，我们在存图时反向存图即可，原本a[i][j]表示i->j，我们可以将它重新定义为j->i，或者存图时直接写成a[j][i]即可。

代码参考

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;

const int maxn = 107;
const int inf = 0x3f3f3f3f; //需将road及dis初始化为正无穷inf
int n,m,k,s;
int dis[maxn];  //储存各个点到源点的最短距离,dis[s]为0
int road[maxn][maxn];   //两点之间直接距离关系
bool vis[maxn];     //判断源点到该点的距离是否为最短距离
int fans[maxn];
void dijkstra(int s)
{
    memset(vis, false, sizeof(vis));
    vis[s] = true;
    for(int i = 1; i <= n; i++)
        dis[i] = road[s][i];
    for(int u = 1; u<n; u++)
    {
        int minD = inf,k = -1;
        for(int i = 1; i<= n; i++)
        {
            if(!vis[i]&&dis[i]<minD)
            {
                k = i;
                minD = dis[i];
            }
        }
        vis[k] = true;
        for(int i = 1; i<= n; i++)
        {
            if(!vis[i]&&dis[k]+road[k][i]<dis[i])
            {
                dis[i]=dis[k]+road[k][i];
            }
        }
    }
}
int main()
{
    cin>>n>>m>>k>>s;
    memset(road,inf,sizeof(road));
    for(int i = 1; i<=m; i++)
    {
        int tmp;
        int x,y;
        cin>>x>>y>>tmp;
        road[y][x]=tmp;
    }
    dijkstra(s);
    for(int i = 0; i<k; i++)
    {
        cin>>fans[i];
    }
    for(int i = 0; i<k-1; i++)
        cout<<dis[fans[i]]<<' ';
    cout<<dis[fans[k-1]]<<endl;
    return 0;
}

问题 D: 躁动的小Z

时间限制: 1 Sec 内存限制: 128 MB
提交: 7 解决: 2
[提交][状态][讨论版][命题人:外部导入][Edit] [TestData)]

题目描述

你猜怎么样？小Z追到Gakki了！Gakki邀请小Z去她家共进晚餐，小Z喜出望外。小Z的家和Gakki的家隔着几个街区，所以他决定乘坐公交车前往

Gakki家赴约。小Z的家在公交站台的起始站（编号为1），而Gakki家正好在末站（编号为n）。城市中有许多公交站台，有些站台之间可以通过公交

线路互相到达。现在给你n个公交站台和m条不同的公交线路的时间花费，请你帮助小Z分析一下最短的可以从家里来到Gakki身边的路径？

输入

有多组测试样例。

第一行两个正整数n,m(2≤n≤10^5,0≤m≤10^5)，代表站台数与公交线路数量。

接下来m行每行三个正整数a[i],b[i],w[i],代表从公交站a[i]到b[i]需要花费的时间为w[i]。(1≤a[i],b[i]≤n,1≤w[i]≤10^6)

注意：公交线路可能会产生环，并且两个站台之间可能有多条公交线路。

输出

单独一行，输出花费时间最小时小Z经过的公交站台编号，以空格隔开；如果小Z无法到达Gakki的家，则输出-1.

样例输入

1
2
3
4
5
6
7
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1

样例输出

1
1 4 3 5

题解

半年前写的代码。其实原理很简单，在dijkstra算法模板的基础上加上一个pre数组，用于记录该节点的上一个节点，即该点是经过哪一点才到达该点的。pre数组具体在边松弛的过程中进行重新赋值，松弛成功就将pre值记录k点，及该点是由起点经过k点后所得到的。最后把pre数组中的值递归输出一遍即可。

代码参考

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>
#include<string.h> 
#include<stdlib.h>
#define max 900000

typedef struct {
	int d; 
	int pre;
}path;
path to[1000 + 2];
int g[1000 + 2][1000 + 2], vis[1000 + 2]; 
void fun(int ddd) {
	if (ddd == 1) {
		printf("%d", ddd);
		return;
	}
	int j= to[ddd].pre;
	fun(j);
	printf(" %d", ddd);
}
int main() {
	int n, m, a, b, v, i, j, min, k, from;
	while (~scanf("%d%d", &n, &m)) { 
		memset(vis, 0, sizeof(vis));
		for (i = 0; i <= n; i++) {
			for (j = 0; j <= n; j++) {
				g[i][j] = max;
			}
			to[i].d = max;
		}
		for (i = 0; i < m; i++) { 
			scanf("%d%d%d", &a, &b, &v);
			g[a][b] = v;
			g[b][a] = v;
		}
		for (i = 2; i <= n; i++) {
			to[i].d = g[1][i];
			if (g[1][i] != max) {
				to[i].pre = 1;
			}
		}
		vis[1] = 1;
		for (i = 2; i <= n; i++) {
			min = max;
			for (j = 2; j <= n; j++) {
				if (to[j].d < min&&vis[j] == 0) {
					min = to[j].d;
					k = j;
				}
			}
			vis[k] = 1;
			for (j = 2; j <= n; j++) {
				if (to[j].d > to[k].d + g[k][j] && vis[j] == 0) {
					to[j].d = to[k].d + g[k][j];
					to[j].pre = k;
				}
			}
		}
		fun(n);
		printf("\n");
	}
	return 0;
}

问题 E: 逛街

时间限制: 1 Sec 内存限制: 128 MB
提交: 8 解决: 2
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

假设渣渣灰有一个女朋友，他的女朋友要他陪着一起去公园。由于渣渣灰不喜欢运动，所以他想找一条最短的路到达公园。由于途中会有许多消费点，而每到一个消费点女朋友就要购物，而渣渣灰比较抠，所以假如有多条最短路，则他会选择途中消费点最便宜的。给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

输入

输入nm，点的编号是1~n然后是m行，每行4个数 abdp，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 st;起点s，终点。n和m为0时输入结束。
(1<n<=1000 0<m<100000 s != t)

输出

输出 一行有两个数， 最短距离及其花费。

样例输入

1
2
3
4
5
6
3 2
1 2 5 6
2 3 4 5
1 3

0 0

样例输出

1
9 11

提示

输入样例的空行只是为了让大家分辨数据，输入有没有空行都没关系。输出样例没有空行。

题解

同上一道题的方法，我们再创建一个value数组储存花费情况。在松弛时对value进行改变。松弛成功则value（s->i）=value(s->k->i)。若最短路相等则对value值进行比较，即value（s->i）=min(value(s->k->i),value（s->i))。s为源点，i为当前终点，k为中间点。最终输出最短路及对应value值即可。

代码参考

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define Min(a,b) a>b?b:a
struct Node
{
	int adj,val;
}g[1005][1005];
int dist[1005];//距离
int value[1005];//费用
int used[1005];//标记
int n,m,i,j;
void Dijkstra(int s)
{
	memset(dist,0x3f,sizeof(dist));
	memset(value,0x3f,sizeof(value));
	memset(used,0,sizeof(used));
	dist[s]=0;//从起点开始
	value[s]=0;
	while(1)
	{
		int k,u=-1,d[1005];
		int min=INF;
		memset(d,0,sizeof(d));
		for(i=1;i<=n;i++)
			if(used[i]==0&&dist[i]<min)//找出从起点到下一个最小距离的顶点
			{
				min=dist[i];
				u=i;//记录下标
			}
		if(u==-1)//判断所有顶点是否都到达过
			return ;
		for(i=1,k=0;i<=n;i++)
			if(dist[u]==dist[i]&&used[i]==0)
				d[k++]=i;//从起点到下一个要访问的顶点的最小距离可能有多个
		for(i=0;i<k;i++)
			used[d[i]]=1;
		for(i=0;i<k;i++)//多个满足的点分别进行迪杰斯特拉最短路查找
			for(j=1;j<=n;j++)
				if(g[d[i]][j].adj!=INF && (dist[d[i]]+g[d[i]][j].adj)<=dist[j])
				{//原理与 main()函数中建立邻接矩阵一样
					if((dist[d[i]]+g[d[i]][j].adj)<dist[j])
						value[j]=value[d[i]]+g[d[i]][j].val;
					else
						value[j]=Min(value[j],value[d[i]]+g[d[i]][j].val);
					dist[j]=dist[d[i]]+g[d[i]][j].adj;
				}
	}
}
int main()
{
	while(scanf("%d%d",&n,&m) && (n||m))
	{
		int a,b,d,p;
		memset(g,0x3f,sizeof(g));
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d%d",&a,&b,&d,&p);
			if(d<=g[a][b].adj)//处理路径距离问题
			{
				if(d==g[a][b].adj)//如果距离相等，则存放最少的费用
					g[a][b].val=g[b][a].val=Min(p,g[a][b].val);
				else//否则，存放新路径距离的费用
					g[a][b].val=g[b][a].val=p;
				g[a][b].adj=g[b][a].adj=d;//填充路径距离
			}
		}
		int s,t;
		scanf("%d%d",&s,&t);
		Dijkstra(s);
		printf("%d %d\n",dist[t],value[t]);
	}
	return 0;
}

问题 F: 足球

时间限制: 1 Sec 内存限制: 128 MB
提交: 3 解决: 1
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

yoyo得到了一个足球，这个足球与其他的足球一样，表面有 12 个正五边形和 20 个正六边形组成，足球的每个面初始的时候都为白色。现在yoyo把这个足球拆解开来，32个面编号为1~32。爱画画的yoyo希望将足球的某些面涂为黑色（可能是 0 个），在每次涂色操作中，慢慢只可以将某一些相邻或者联通的面一起涂为黑色（两个面相邻当且仅当他们共用一条边）。例如，yoyo可以在一次涂色操作中将面 1、2、3、4、5 涂为黑色，但是他不可以将面11 和 24 涂为白色，因为面 11 和 24 是不相邻也不联通的。求yoyo所需要的最少的涂色次数。

输入

第一行包含一个整数 t，表示有t组测试数据，对于每组测试数据：

输入包含一行，该行包含 32 个整数，每个数的值等于 0 时表示白色，等于 1 时表示黑色。

输出

对于每组测试数据，输出Case c: ans，其中 c 为测试数据编号，ans 为最少的操作次数。

样例输入

1
2
3
4
3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

样例输出

1
2
3
Case 1: 1
Case 2: 0
Case 3: 2

提示

除了相邻的数面也相邻外，面 1 和面 13 是相邻的，面 13 和面 17 是相邻的，面 17 和面 32 是相邻的，面 15 和面 32 是相邻的，面 19 和面 32 是相邻的。

PS:1和32不相邻。

题解

先把所有相邻的点赋值为1，再用Floyd算法把所有点之间的最短距离打表求出来。之后每输入一组样例，则对样例中的1dfs深搜，然后深搜把所有相邻为1且值为1的点重新赋值为0。最后记录下主循环中dfs的次数即可。

代码参考

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
const int maxn = 32 + 1;
int dis[maxn][maxn];
int vis[maxn];
void init(){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[32][32] = 0;
    for(int i = 1; i < maxn - 1; i++){
        dis[i][i] = 0;
        dis[i][i + 1] = 1;
        dis[i + 1][i] = 1;
    }
    dis[1][13] = dis[13][1] = 1;
    dis[17][13] = dis[13][17] = 1;
    dis[17][32] = dis[32][17] = 1;
    dis[15][32] = dis[32][15] = 1;
    dis[19][32] = dis[32][19] = 1;
    for(int k = 1; k < maxn; k++){
        for(int i = 1; i < maxn; i++)
            for(int j = 1; j < maxn; j++)
                if(dis[i][j] > dis[i][k]+dis[k][j])
                    dis[i][j] = dis[i][k]+dis[k][j];
    }
}
void dfs(int x){
    vis[x] = 0;
    for(int i = 1; i < maxn; i++){
        if(vis[i]&&dis[x][i]==1)
            dfs(i);
    }
}
int main(){

    init();
    int t;
    cin>>t;
    for(int u = 1;u <= t;u++){
        for(int i = 1;i < maxn; i++)
            cin>>vis[i];
        int ans = 0;
        for(int i = 1; i < maxn; i++){
            if(vis[i]){
                ans++;
                dfs(i);
            }
        }
        cout<<"Case "<<u<<": "<<ans<<endl;
    }
    return 0;
}

问题 G: 牌

时间限制: 1 Sec 内存限制: 128 MB
提交: 2 解决: 2
[提交][状态][讨论版][命题人:qianyouyou][Edit] [TestData)]

题目描述

有n张牌，每个牌有一个a属性和1个b属性，第i张牌的属性为ai，bi。现在每次从牌中选两张牌i，j，得到一个ai bj + bi aj的分数，然后从这两张牌中去掉1张牌。经过n-1次操作之后就剩1张牌了。问经过n-1次操作后得到的最大的分数和是多少。

输入

首行输入n，代表n个点

接下来n行，每一行两个属性ab第i行代表第i张牌，属性为ai，bi。数据范围保持在200以内。

输出

输出最大分数

样例输入

1
2
3
4
5
6
5
2 4
3 3
1 7
2 5
4 4

样例输出

1
108

题解

主要是删除牌的问题。但是假如我们将每张牌看成1个结点，属性的乘积得到的分数为1条路径，那么n张牌构成了n个结点n*（n-1）/2条边的强联通无向图，那么只需求每次分数最大的最小生成树即可。

代码参考

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>
#include<string.h> 
#include<stdlib.h>
#define max 900000

typedef struct {
	int d; 
	int pre;
}path;
path to[1000 + 2];
int g[1000 + 2][1000 + 2], vis[1000 + 2]; 
void fun(int ddd) {
	if (ddd == 1) {
		printf("%d", ddd);
		return;
	}
	int j= to[ddd].pre;
	fun(j);
	printf(" %d", ddd);
}
int main() {
	int n, m, a, b, v, i, j, min, k, from;
	while (~scanf("%d%d", &n, &m)) { 
		memset(vis, 0, sizeof(vis));
		for (i = 0; i <= n; i++) {
			for (j = 0; j <= n; j++) {
				g[i][j] = max;
			}
			to[i].d = max;
		}
		for (i = 0; i < m; i++) { 
			scanf("%d%d%d", &a, &b, &v);
			g[a][b] = v;
			g[b][a] = v;
		}
		for (i = 2; i <= n; i++) {
			to[i].d = g[1][i];
			if (g[1][i] != max) {
				to[i].pre = 1;
			}
		}
		vis[1] = 1;
		for (i = 2; i <= n; i++) {
			min = max;
			for (j = 2; j <= n; j++) {
				if (to[j].d < min&&vis[j] == 0) {
					min = to[j].d;
					k = j;
				}
			}
			vis[k] = 1;
			for (j = 2; j <= n; j++) {
				if (to[j].d > to[k].d + g[k][j] && vis[j] == 0) {
					to[j].d = to[k].d + g[k][j];
					to[j].pre = k;
				}
			}
		}
		fun(n);
		printf("\n");
	}
	return 0;
}

常用模板代码

拓扑排序

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
const int maxn=510;
int graph[maxn][maxn];//保存图
int degree[maxn];//保存入度
int TOP[maxn];//保存已删除点
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
    	int now = 0；//指针作用记录TOP中可插入的位置
        memset(graph,0,sizeof(graph));
        memset(degree,0,sizeof(degree));
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            if(!graph[u][v])
            {
                graph[u][v]=1;
                degree[v]++;//v的入度++
            }
        }
        queue<int>q;
        for(int i=1;i<=n;i++)
            if(degree[i]==0)
            q.push(i);
        while(!q.empty())
        {
            int cur=q.front();
            q.pop();
            TOP[now++]=cur;
            for(int i=1;i<=n;i++)
            {
                if(graph[cur][i]==1)
                {
                    degree[i]--;//相连的点的入度减1
                    if(degree[i]==0)//假设入度为0，增加队列
                        q.push(i);
                }
            }
        }
        //这里可以添加输出，排序已保存在TOP数组中
    }
    return 0;
}

dijkstra（单元最短路径）

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;

const int maxn = 107;
const int inf = 0x3f3f3f3f; //需将road及dis初始化为正无穷inf
int n,m,k,s;
int dis[maxn];  //储存各个点到源点的最短距离,dis[s]为0
int road[maxn][maxn];   //两点之间直接距离关系
bool vis[maxn];     //判断源点到该点的距离是否为最短距离

void dijkstra(int s)
{
    memset(vis, false, sizeof(vis));
    vis[s] = true;
    for(int i = 1; i <= n; i++)
        dis[i] = road[s][i];
    for(int u = 1; u<n; u++)
    {
        int minD = inf,k = -1;
        for(int i = 1; i<= n; i++)
        {
            if(!vis[i]&&dis[i]<minD)
            {
                k = i;
                minD = dis[i];
            }
        }
        vis[k] = true;
        for(int i = 1; i<= n; i++)
        {
            if(!vis[i]&&dis[k]+road[k][i]<dis[i])
            {
                dis[i]=dis[k]+road[k][i];
            }
        }
    }
}
int main()
{
    
    memset(road,inf,sizeof(road));
    //主函数添加程序与数据以及调用dijkstra
    return 0;
}

SPFA（单元最短路径，可带负环）

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
31
32
33
34
35
#include<bits/stdc++.h>
#define N 105
int res[N];//存储源点到每个顶点的最短距离值
int g[N][N];
int cnt[N];//每个点入队次数，判断是否出现负环
int que[N*N];//队列
bool in_que[N];//标记一个点是否已在队列中
int front;//队首位置
int rear;//队尾位置
void spfa(int n,int src)
{
    rear=front=0;
    que[++rear]=src;
    memset(res,0x3f3f3f3f,sizeof(res));
    memset(in_que,0,sizeof(in_que));
    res[src]=0;
    while(front<rear)
    {
        int cur=que[++front];
        in_que[cur]=0;
        int i;
        for(i=1; i<=n; i++)
        {
            if(res[cur]+g[cur][i]<res[i])
            {
                res[i]=res[cur]+g[cur][i];
                if(!in_que[i])
                {
                    que[++rear]=i;
                    in_que=1;
                }
            }
        }
    }
}

Floyed（全源最短路径）

1
2
3
4
5
6
7
8
9
for (int k=0; k<n; ++k)
  for (int i=0; i<n; ++i)
    for (int j=0; j<n; ++j)
            /*
            实际中为防止溢出，往往需要选判断 dist[i][k]和dist[k][j]
            都不是Inf ，只要一个是Inf，那么就肯定不必更新。 
            */
      if (dist[i][k] + dist[k][j] < dist[i][j] )
        dist[i][j] = dist[i][k] + dist[k][j];

Prim最小生成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Prim(){
	int i,j,k,tmp,ans;
	for(i=1;i<=n;i++)
	dis[i]=inf;//初始化 
	dis[1]=0;
	for(i=1;i<=n;i++){
		tmp=inf;
		for(j=1;j<=n;j++){
			if(!vis[j]&&tmp>dis[j]){
				tmp=dis[j];
				k=j;
			}//找出最小距离的节点 
		}
		vis[k]=1;//把访问的节点做标记
		for(j=1;j<=n;j++){
			if(!vis[j]&&dis[j]>map[k][j])
			dis[j]=map[k][j];//更新最短距离 
		}
	}
}

kruskal

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1007;
int n,m;
struct Edge
{
    int x;
    int y;
    int l;
} edge[maxn];
int fa[maxn];
int init()
{
    for(int i = 0; i<maxn; i++)
        fa[i] = i;
}
int findfa(int x)
{
    return fa[x] == x ? x : (fa[x] = findfa(fa[x]));
}

int merge_1(int x,int y)
{
    fa[findfa(x)] = findfa(y);
}
int kruskal()
{
    int cnt = 0;
    int sum = 0;
    for(int i = 0; i<= m; i++)
    {
        int fx = findfa(edge[i].x);
        int fy = findfa(edge[i].y);
        if(fx!=fy)
        {
            merge_1(fx,fy);
            cnt++;
            sum+=edge[i].l;
            if(cnt>=n-1)
                break;
        }
    }
    cout<<sum<<endl;
}
int main()
{
    init();
    //此处填写边以及点等待输入数据，填写完成后须对边的权值进行排序
    kruskal();
    return 0;
}
文章结束了，但我们的故事还在继续
坚持原创技术分享，您的支持将鼓励我继续创作！