1. AI技术聚合首页
  2. IT

《图》经典题题解（拓扑排序，DFS，BFS，Floyd,Dijkstra,LCA最近公共祖先，最小生成树，最短路径）（ACM）

心中带点小风骚 • • IT • 阅读 33

目录

拓扑排序 / 家谱树

题目链接：B3644 【模板】拓扑排序 / 家谱树 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

A - 拓扑排序 / 家谱树
https://www.luogu.com.cn/problem/B3644

vector<int>edeg[101];//每个点的链，存了该点连接到的所有点，便于删除其出去的边
int n, deg[101] = { 0 };//入度
void init()//建图
{
    cin >> n;
    int i, val;
    for (i = 1; i <= n; i++)
    {
        while (cin >> val && val != 0)
        {
            edeg[i].push_back(val);
            deg[val]++;
        }
    }
}

void toposort()//拓扑排序
{
    int i;
    queue<int> que;//存入度已经为0的点，方便删除出去的边
    for (i = 1; i <= n; i++)
    {
        if (deg[i] == 0)
        {
            cout << i << ' ';
            que.push(i);
        }
    }

    while (!que.empty())
    {
        int t = que.front();
        que.pop();

        for (int i : edeg[t])
        {
            deg[i]--;
            if (deg[i] == 0)
            {
                cout << i << ' ';
                que.push(i);
            }
        }
    }
}

int main()
{
    init();//建图
    toposort();//拓扑排序
    return 0;
}

p1359租用潜艇

题目链接：
租用游艇 – 洛谷

Floyd的用法，同时涉及了dp


P1359 租用游艇
https://www.luogu.com.cn/problem/P1359
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

//半矩阵：三角矩阵

const int N = 200 + 5;
int board[N][N];

int main()
{
	quickio;
	int n;
	cin >> n;
	int i, j;
	int dp[N] = { 0 };//dp[i]：存的是从i点到n点的最短距离

	for (i = 1; i < n; i++)
	{
		for (j = i + 1; j <= n; j++)
		{
			cin >> board[i][j];
		}
		dp[i] = 1e6;
	}
	
	//注意要倒着跑
	for (i = n - 1; i >= 1; i--)
	{
		for (j = i + 1; j <= n; j++)
		{
			dp[i] = min(dp[i], dp[j] + board[i][j]);
		}
	}

	cout << dp[1] << endl;
	return 0;
}

P1938[USACO09NOV] Job Hunt S 

题目链接：[USACO09NOV] Job Hunt S – 洛谷

题目思路：将工资加在路径的权值中，求的是最长路径—->工资最多


P1938[USACO09NOV] Job Hunt S
// //https://www.luogu.com.cn/problem/P1938
//单源最长路径

//注意Dij不可以用于负边的情况


#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>#include <unordered_set>#include <map>#include <set>#include <queue>#include <stack>#include <deque>#include <functional>#include <climits>
#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);#define endl "\n"
using namespace std;typedef long long ll;
const int N = 220 + 5;const int M = 150 + 350 + 5;
int head[N];//链的个数int cnt;int vis[N];int dis[N];int countx[N];
int D, P, C, F, S;
struct EDGE
{
	int v;
	int next;
	int w;
}EDGE[M];//
void add(int u, int v, int w){
	cnt++;
	EDGE[cnt].v = v;
	EDGE[cnt].w = w;
	EDGE[cnt].next = head[u];
	head[u] = cnt;
}
//该题不同点：求的是最长路径
void SPFA(){
    queue<int>que;//存点
    que.push(S);
    memset(dis, 0, sizeof(dis));
    dis[S] =  D;
    vis[S] = 1;
    
    while (!que.empty())
    {
        int dian = que.front();
        que.pop();
        vis[dian] = 0;/**/
        countx[dian]++;
        if (countx[dian] == C)
        {
            cout << -1 << endl;
            exit(0);
        }
        
        for (int j = head[dian]; j; j = EDGE[j].next)
        {
            if (dis[dian] + EDGE[j].w > dis[EDGE[j].v])
            {
                dis[EDGE[j].v] = dis[dian] + EDGE[j].w;
                
                if (vis[EDGE[j].v] == 0)
                {
                    que.push(EDGE[j].v);
                    vis[EDGE[j].v] = 1;
                }
            }
        }
    }
}
int main(){
	quickio;
	cin >> D >> P >> C >> F >> S;
	
	int i, u, v, w;
	for (i = 0; i < P; i++)
	{
	    cin >> u >> v;
	    add(u, v, D);/**/
	}
	for (i = 0; i < F; i++)
	{
	    cin >> u >> v >> w;
	    add(u, v, D - w);/**/
	}
	
	SPFA();
	
	int maxx = INT_MIN;
	for (i = 1; i <= C; i++)
	{
	    maxx = max(maxx, dis[i]);
	}
	cout << maxx << endl;
	
	return 0;
}

最短路计数

题目链接：
最短路计数 – 洛谷

题目思路：多用了一个countx数组计数，也注意mod的运用


最短路计数
//最短路计数
//https://www.luogu.com.cn/problem/P1144
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>
#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"
using namespace std;typedef long long ll;
const int N = 1e6 + 5;const int M = 2e6 + 5;
int head[N*2];//链的个数
int cnt;int vis[N*2];
int ans[N*2];
int countx[N*2];
struct EDGE
{
	int to;
	int next;
	int w;
}edge[M*2];//
void add(int u, int v, int w){
	cnt++;
	edge[cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt;
}
void Dij(){
	priority_queue<pair<int, int> >que;
    que.push({0, 1});
    ans[1] = 0;
    countx[1] = 1;
    
    while (!que.empty())
    {
        int dis = que.top().first;
        int dian = que.top().second;
        que.pop();
        
        if (vis[dian])
            continue;
            
        vis[dian] = 1;
        
        for (int j = head[dian]; j; j = edge[j].next)
        {
            if (ans[dian] + edge[j].w < ans[edge[j].to])
            {
                ans[edge[j].to] = ans[dian] + edge[j].w;
                countx[edge[j].to] = countx[dian];
                
                    que.push({-ans[edge[j].to], edge[j].to});
            }
            else if (ans[dian] + edge[j].w == ans[edge[j].to])
            {
                countx[edge[j].to] = (countx[edge[j].to] %100003 + countx[dian]%100003)%100003;
                countx[edge[j].to] %= 100003;
            }
        }
    }
	
}
int main(){
	quickio;
	int n, m;
	cin >> n >> m;

	int i;
	int u, v;
	for (i = 1; i <= m; i++)
	{
		cin >> u >> v;
		add(u, v, 1);
		add(v, u, 1);//注意是无向边
	}

	memset(ans, 0x3f, sizeof(ans));

	Dij();

	for (i = 1; i <= n; i++)
		cout << countx[i] << endl;

	return 0;
}

797. 所有可能的路径 

Dfs模板：

Dfs，和深搜一样的模板
void dfs(参数)
{
    if (终止条件)
    {
        处理结果；
        return;
     }

    for(该层元素)
    {
        处理节点；
        DFS；
        处理结果
    }
}

题目链接： . – 力扣（LeetCode）


797. 所有可能的路径
//https://leetcode.cn/problems/all-paths-from-source-to-target/

//图：一般一维数组存路径，二维数组存所有结果

class Solution {
public:
    vector<vector<int> >res;
    vector<int> path;

    void dfs(vector<vector<int>>& graph, int cur/*当前所在的点*/)
    {
        if (cur == graph.size() - 1)
        {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < graph[cur].size(); i++)
        {
            path.push_back(graph[cur][i]);
            dfs(graph, graph[cur][i]);
            path.pop_back();
        }
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) 
    {
        path.push_back(0);
        dfs(graph, 0);
        return res;
    }
};

200.岛屿数量

知识点：

BFS，和Dij的优先队列类似

DFS和BFS都要用到to数组(存四个走向)

满足条件的加入队列或者dfs继续深搜

要用到vis数组，标记已经遍历过的点

题目链接：. – 力扣（LeetCode）

DFS


200. 岛屿数量
//https://leetcode.cn/problems/number-of-islands/

//题意：只要周边都是水，就算一个岛屿
//只有四个方向可以走

//深搜：用一个计数器，记录连接在一起的陆地数量，当不是陆地时并且遍历完所属区域时，返回
class Solution {
public:
    int to[4][2] = {{0, 1}, {1, 0},{-1, 0}, {0, -1}};
    int vis[305][305] = { 0 };
    int count = 0;

    void dfs(vector<vector<char>>& grid, int x, int y)
    {
        //没有终止条件的原因：下面的循环中就对继续深搜设置了条件，不满足条件的不继续搜

        for (int i = 0; i < 4; i++)
        {
            int nextx = x + to[i][0];
            int nexty = y + to[i][1];

            if (nextx < 0 ||  nexty < 0 || nextx >= grid.size() || nexty >= grid[0].size())
                continue;

            if (grid[nextx][nexty] == '1' && vis[nextx][nexty] == 0)
             {
               vis[nextx][nexty] = 1;
               dfs(grid, nextx, nexty);
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) 
    {
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[i].size(); j++)
            {
                if (vis[i][j] == 0 && grid[i][j] == '1')
                {
                    count++;
                    vis[i][j] = 1;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
};

BFS


//广搜：用队列，有模板：最短路径模板
class Solution {
public:
    int to[4][2] = {{0, 1}, {1, 0},{-1, 0}, {0, -1}};
    int vis[305][305] = { 0 };
    int count = 0;

    void bfs(vector<vector<char>>& grid)
    {
        queue<pair<int, int> >que;

        for (int p = 0; p < grid.size(); p++)
        {
            for (int q = 0; q < grid[p].size(); q++)
            {
                if (vis[p][q] == 0 && grid[p][q] == '1')
                {
                    count++;
                    que.push({p, q});
                    while (!que.empty())
                    {
                        int x = que.front().first;
                        int y = que.front().second;
                        que.pop();
                        vis[x][y] = 1;

                        for (int i = 0; i < 4; i++)
                        {
                            int nextx = x + to[i][0];
                            int nexty = y + to[i][1];

                            if (nextx < 0 ||  nexty < 0 || nextx >= grid.size() || nexty >= grid[0].size())
                                continue;
                            
                            if (vis[nextx][nexty] == 0 && grid[nextx][nexty] == '1')
                            {
                                que.push({nextx, nexty});
                                vis[nextx][nexty] = 1;
                            }
                        }
                    }
                }
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) 
    {
        bfs(grid);
        return count;
    }
};

695.岛屿的最大面积

题目链接：. – 力扣（LeetCode）

DFS

695. 岛屿的最大面积
//https://leetcode.cn/problems/max-area-of-island/

//仍然两种图遍历方法都能写，dfs:层数计数，bfs:队列大小计数

//dfs
class Solution {
public:
    int count = 0;
    int vis[55][55] = { 0 };/*必需*/
    int to[4][2] = { 0, 1, 1, 0, -1, 0, 0, -1 };/*必需*/
    int temp;

    void dfs(vector<vector<int>>& grid, int x, int y)
    {
        //也是在后面就把回溯条件给确定了，不满足的就不会来递归
        if (temp > count)
            count = temp;

        for (int i = 0; i < 4; i++)
        {
            int nextx = x + to[i][0];
            int nexty = y + to[i][1];

            if (nextx < 0 || nexty < 0 || nextx >= grid.size() || nexty >= grid[0].size())
                continue;

            if (vis[nextx][nexty] == 0 && grid[nextx][nexty] == 1)
            {
                vis[nextx][nexty] = 1;
                temp++;
                dfs(grid, nextx, nexty);
            }
        }
    }

    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[i].size(); j++)
            {
                if (vis[i][j] == 0 && grid[i][j] == 1)
                {
                    vis[i][j] = 1;
                    temp = 1;/*注意是1*/
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
};

BFS


//BFS
class Solution {
public:
    int count = 0;
    int vis[55][55] = { 0 };/*必需*/
    int to[4][2] = { 0, 1, 1, 0, -1, 0, 0, -1 };/*必需*/
    int temp;

    void BFS(vector<vector<int>>& grid)
    {
        queue<pair<int, int> > que;
        int temp;
        
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[i].size(); j++)
            {
                if (vis[i][j] == 0 && grid[i][j] == 1)
                {
                    que.push({i, j});
                    temp = 1;
                    while (!que.empty())
                    {
                        int x = que.front().first;
                        int y = que.front().second;
                        que.pop();
                        vis[x][y] = 1;

                        for (int p = 0; p < 4; p++)
                        {
                            int nextx = x + to[p][0];
                            int nexty = y + to[p][1];

                            if (nextx < 0 || nexty < 0 || nextx >= grid.size() || nexty >= grid[0].size())
                                continue;

                            if (vis[nextx][nexty] == 0 && grid[nextx][nexty] == 1)
                            {
                                vis[nextx][nexty] = 1;
                                temp++;
                                que.push({nextx, nexty});
                            }
                        }
                    }
                    count = max(count, temp);
                }
            }
        }
    }

    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        BFS(grid);
        
        return count;
    }
};

P1119 灾后重建 

题目链接：灾后重建 – 洛谷

P1119 灾后重建
注意z是一直增大的，所以可以用一个cnt再每次询问时更新并且同时更新board里存的最短路径，
因为一开始board初始化为INT_MAX,所以注意两个board元素加一起的时候用int存储会导致答案错误，因此要board设置为ll
//https://www.luogu.com.cn/problem/P1119

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;


const int N = 205;
const int M = 20005;

ll board[N][N];/*注意数组必须开ll，否则加起来超过int，就答案与原来不符*/

int t[N];
int n, m;

void Floyd(int k)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (board[i][k] == INT_MAX || board[k][j] == INT_MAX)
				continue;
			if (board[i][k] + board[k][j] < board[i][j])
				board[i][j] = board[j][i] = board[i][k] + board[k][j];
		}
	}
}

int main()
{
	quickio;
	cin >> n >> m;
	int i;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			board[i][j] = INT_MAX;
		}
	}

	for (i = 0; i < n; i++)
	{
		cin >> t[i];
		board[i][i] = 0;
	}


	int u, v, w;
	while (m--)
	{
		cin >> u >> v >> w;
		board[u][v] = board[v][u] = w;
	}

	int q;
	cin >> q;
	int x, y, z;
	int cnt = 0;
	while (q--)
	{
		cin >> x >> y >> z;
		
		while (t[cnt] <= z && cnt < n)
		{
			Floyd(cnt);
			cnt++;
		}

		if (z < t[x] || z < t[y])
		{
			cout << -1 << endl;
		}
		else
		{
			if (board[x][y] != INT_MAX)
				cout << board[x][y] << endl;
			else
				cout << -1 << endl;
		}
	}

	return 0;
}

P1629 邮递员送信

题目链接：邮递员送信 – 洛谷

法一：Floyd

超时

P1629 邮递员送信
建反图，注意要将各个数组开为平时写的两倍，否则存不下
//https://www.luogu.com.cn/problem/P1629

/*法一：Floyd*/
//两个样例超时

//#include <climits>
//#include <iostream>
//
//using namespace std;
//
//const int MAX = 1010;
//int board[MAX][MAX];
//
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//
//    int i, j;
//    for (i = 1; i <= n; i++)
//    {
//        for (j = 1; j <= n; j++)
//        {
//            if (i == j)
//                board[i][j] = 0;
//            else
//                board[i][j] = INT_MAX;
//        }
//    }
//
//    int u, v, w;
//    for (i = 1; i <= m; i++)
//    {
//        cin >> u >> v >> w;
//        if (w < board[u][v])
//            board[u][v] = w;
//    }
//
//    int k;
//    for (k = 1; k <= n; k++)
//    {
//        for (i = 1; i <= n; i++)
//        {
//            if (i == k)
//                continue;
//            for (j = 1; j <= n; j++)
//            {
//                if (j == k)
//                    continue;
//
//                if (i == j)
//                    continue;
//
//                if (board[i][k] != INT_MAX && board[k][j] != INT_MAX)
//                {
//                    if (board[i][k] + board[k][j] < board[i][j])
//                        board[i][j] = board[i][k] + board[k][j];
//                }
//            }
//        }
//    }
//
//    int sum = 0;
//    for (i = 2; i <= n; i++)
//    {
//        sum += board[i][1] + board[1][i];
//    }
//    cout << sum << endl;
//    return 0;
//}

法二：Dijkstra


/*法二：dijkstra*/
//反向建图

//按题中给的示例：1 -> 2 -> 3 -> 5 -> 4 ->1，建返图后就是 1 -> 2 + 6 -> 9 -> 10 -> 8

/*注意MAX的值设定，因为最大权值可以到达1e4，然后边数可以到达1e5，所以至少要大于1e9*/
/*!!!!!涉及链式前向星!!!!!!!!*/
/*
链式前向星
*/
/*注意各个数组大小的设定*/

#include <iostream>
#include <queue>
#include <climits>
#include <stdlib.h>
#include <string.h>

using namespace std;

const int MAXM = 100005;
const int MAXN = 1005;
int head[MAXN * 2];//每个点的链
int cnt;
int ans[MAXN * 2];//起点 到 该点最短路径
int vis[MAXN * 2];//是否该点被加入进最短路径中

struct EDGE
{
    int to;
    int next;
    int wei;
}edge[MAXM * 2];/*每条边的数据*/

void add(int u, int v, int w)//创建边 的函数
{
    cnt++;
    edge[cnt].to = v;
    edge[cnt].wei = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

void dij(int s)//求 s 到 各个点 的最短路径
{
    priority_queue<pair<int, int> >que;//距离， 点号

    que.push({ 0, s });

    while (!que.empty())
    {
        int h = que.top().first;//距离
        int ph = que.top().second;//点
        que.pop();

        if (vis[ph] == 0)
        {
            vis[ph] = 1;
            for (int i = head[ph]; i != 0; i = edge[i].next)
            {
                if (ans[edge[i].to] > ans[ph] + edge[i].wei)
                {
                    ans[edge[i].to] = ans[ph] + edge[i].wei;

                    if (vis[edge[i].to] == 0)
                    {
                        que.push({ - ans[edge[i].to], edge[i].to});
                    }
                }
            }
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    int i;

    for (i = 1; i <= n; i++)
    {
        ans[i] = INT_MAX;
    }
    ans[1] = 0;

    int u, v, w;
    for (i = 1; i <= m; i++)
    {
        cin >> u >> v >> w;
        add(u, v, w);
        add(v + n, u + n, w);//建反边！！！！！！！！！！重点
    }

    dij(1);
    int sum = 0;
    for (i = 2; i <= n; i++)
        sum += ans[i];

    memset(vis, 0, sizeof vis);
    for (i = 1 + n; i <= n + n; i++)
    {
        ans[i] = INT_MAX;
    }
    ans[1 + n] = 0;

    dij(1 + n);
    for (i = 2 + n; i <= n + n; i++)
        sum += ans[i];

    cout << sum << endl;
    return 0;
}

P3379 【模板】最近公共祖先（LCA）

题目链接:【模板】最近公共祖先（LCA） – 洛谷

//P3379 【模板】最近公共祖先（LCA）
//https://www.luogu.com.cn/problem/P3379
//倍增法求最近公共祖先
//1.朴素（先跳到同意深度，再都往上找，第一次相遇的点就算最近公共祖先）//2.LAC（找2的次方个父亲） //3.Tarjan(用了并查集)
//（先将询问放到相应节点的叶子节点下，当该枝遍历完后
//，找询问是否已经被并再某个并查集，若并了，
//则所在并查集就是其公共祖先）
//每过一个节点就放入并查集一次，再继续递归
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>
#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);#define endl "\n"
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
const int M = 5e5 + 5;
int head[N * 2];
int cnt;

int n, m, s;
int f[N][30];//f[i][j]:i点的第2^j个父亲，注意是30，不是20
int dep[N];//深度

struct EDGE
{
	int v;
	int next;
}EDGE[M * 2];
void add(int u, int v){
	cnt++;
	EDGE[cnt].v = v;
	EDGE[cnt].next = head[u];
	head[u] = cnt;
}
void dfs(int v, int father)//孩子，父亲{
    dep[v] = dep[father] + 1;//孩子深度= 父亲深度 + 1
    f[v][0] = father;//父亲一定是孩子的第1个父亲，也就是2^0个
    for (int i = 1/*注意从1开始*/; (1 << i)/*2的i次方*/ <= dep[v]; i++)
    {
        f[v][i] = f[f[v][i - 1]][i - 1];/*公式*/
    }
    
    //注意把v的孩子的情况也要处理
    for (int j = head[v]; j; j = EDGE[j].next)
    {
        if (EDGE[j].v != father)/*!!!!!!!!!!!!!!!!!!!!*/
            dfs(EDGE[j].v, v);
    }
}
int LCA(int x, int y){
    if (dep[x] < dep[y])//注意x要比y下面
        swap(x, y);
        
    //先将x, y调到同一层
    for (int i = 20; i >= 0; i--)
    {
        if (dep[f[x][i]] >= dep[y])
        //如果x的第i个父亲的深度 > y的深度，就更新x
            x = f[x][i];
    }
    if (x == y)
    //说明x, y中有一点就算公共祖先
        return x;
        
    //移到公共祖先的下一层
    for (int i = 20; i >= 0; i--)
    {
        if (f[x][i] != f[y][i])
        //注意两者不能重合，最多只能移动到公共祖先的下一层
        {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];//上一层就是公共祖先
}
int main(){
	quickio;
	cin >> n >> m >> s;
	int i;

	int x, y;
	for (i = 0; i < n - 1; i++)
	{
		cin >> x >> y;
		add(x, y);
		add(y, x);/*注意是双边，不仅注意要反向添加
		还要把数组大小初始化两倍*/
	}

	dfs(s,0);//根节点，0（因为没有0节点，所以0节点表示根节点父亲）

	int a, b;
	while (m--)
	{
		cin >> a >> b;
		cout << LCA(a, b) << endl;
	}

	return 0;
}

最小生成树

题目链接：【模板】最小生成树 – 洛谷

法一：prim算法

P3366 【模板】最小生成树
//https://www.luogu.com.cn/problem/P3366

prim算法
// 注意都是无向边
//要用到d[N]:存某点到圈外点的最短距离，vis[N]：存某点是否出圈，出圈了就标记为1
//ans:记录最小生成树的值
//countx:记录加入生成树的点数，只要该点的d[]不等于inf，count就++
//初始化：一开始除了起点都初始化为inf

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

const int N = 5005;
const int M = 2e5 + 5;

int head[N * 2];//注意是无向边
int cnt;
int vis[N];
int d[N];

int ans;//记录最小生成树的各边长度之和
int countx;//记录加入最小生成树的节点个数

int n, m;

struct EDGE
{
	int v;
	int w;
	int next;
}EDGE[M * 2];

void add(int u, int v, int w)
{
	cnt++;
	EDGE[cnt].v = v;
	EDGE[cnt].w = w;
	EDGE[cnt].next = head[u];
	head[u] = cnt;
}

bool prim(int s)
{
	priority_queue<pair<int, int> >que;
	que.push({ 0, s });
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;

	while (!que.empty())
	{
		int dis = -que.top().first;
		int dian = que.top().second;
		que.pop();

		if (dis != d[dian])
			continue;

		if (vis[dian] == 0)
		{
			vis[dian] = 1;
			if (d[dian] != 0x3f3f3f3f)
				countx++;
			
			ans += d[dian];
			for (int j = head[dian]; j; j = EDGE[j].next)
			{
				int t = EDGE[j].v;
				int w = EDGE[j].w;
				if (vis[t] == 0 && d[t] > w)
				{
					d[t] = w;
					que.push({ -d[t], t });
				}
			}
		}
	}
	return countx == n;
}

int main()
{
	quickio;
	cin >> n >> m;
	int u, v, w;
	for (int i = 1; i <= m; i++)
	{
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}

	prim(1);

	if (countx == n)
		cout << ans << endl;
	else
		cout << "orz" << endl;
	return 0;
}

法二：Kruskal算法

法二：Kruskal算法

//用到了并查集，并且排序了所有边----->贪心思想----->最小边就有可能构成最小生成树

//步骤：
//初始化并查集（每个节点的父节点都是自己）
//按边权从小到大排序（用到sort和重载<）
//按顺序枚举每一条边，如果这条边连接的两个点不在同一集合，就将其加入最小生成树，并且合并两棵树

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

const int M = 2e5 + 5;
const int N = 5005;

//int head[N];
//int d[N];
int fa[N];
int cnt;
int ans;//存最小生成树答案
int countx;//存边数

int n, m;

struct EDGE
{
	int u;/*注意，多了个u*/
	int v;
	int w;
	//int next;
	bool operator<(const EDGE& t)
	{
		return w < t.w;
	}
}EDGE[M * 2];//注意是无向边

int find(int x)
{
	if (fa[x] == x)
		return x;
	return fa[x] = find(fa[x]);
}

void add(int u, int v, int w)
{
	cnt++;
	EDGE[cnt].v = v;
	EDGE[cnt].w = w;
	//EDGE[cnt].next = head[u];
	EDGE[cnt].u = u;
	//head[u] = cnt;
}

bool Kruskal()
{
	sort(EDGE + 1, EDGE + 1+ m);

	for (int i = 1; i <= m; i++)
	{
		int x = find(EDGE[i].u);
		int y = find(EDGE[i].v);

		if (x != y)
		{
			fa[x] = y;/*注意是等于y，不是等于fa[y]*/
			ans += EDGE[i].w;
			countx++;
		}
	}

	return countx == n - 1;
}

int main()
{
	quickio;
	cin >> n >> m;
	int u, v, w;
	for (int i = 0; i< m; i++)
	{
		cin >> u >> v >> w;
		add(u, v, w);
		//add(v, u, w);/*!!!!!!!!注意，不要建双向边!!!!!!!!*/
	}

	for (int i = 1; i <= n; i++)
		fa[i] = i;

	bool res = Kruskal();

	if (res)
	{
		cout << ans << endl;
	}
	else
		cout << "orz" << endl;
	return 0;
}

P1546 [USACO3.1] 最短网络 Agri-Net

题目链接：[USACO3.1] 最短网络 Agri-Net – 洛谷

P1546 [USACO3.1] 最短网络 Agri-Net
//https://www.luogu.com.cn/problem/P1546

//和最小生成树一样的思路p----->prim算法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

const int N = 105;
const int M = 10000000;

//int board[N][N];
int d[N];
int ans;
int cnt;
int countx;
int head[N];
int vis[N];

int n;

struct EDGE
{
	int v;
	int w;
	int next;
}EDGE[M * 2];

void add(int u, int v, int w)
{
	cnt++;
	EDGE[cnt].next = head[u];
	EDGE[cnt].v = v;
	EDGE[cnt].w = w;
	head[u] = cnt;
}

void prim(int s)
{
	priority_queue<pair<int, int> >que;
	que.push({ 0, s });
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;

	while (!que.empty())
	{
		int dis = -que.top().first;
		int dian = que.top().second;
		que.pop();

		if (dis != d[dian])
			continue;

		if (d[dian] != 0x3f3f3f3f)
			countx++;
		ans += d[dian];
		if (vis[dian] == 0)
		{
			vis[dian] = 1;

			for (int j = head[dian]; j; j = EDGE[j].next)
			{
				int t = EDGE[j].v;
				int w = EDGE[j].w;

				if (vis[t] == 0 && d[t] > w)
				{
					d[t] = w;
					que.push({ -d[t], t });
				}
			}
		}
	}
}

int main()
{
	quickio;
	cin >> n;
	int w;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			//cin >> board[i][j];
			cin >> w;
			add(i, j, w);
			add(j, i, w);
		}
	}
	prim(1);

	cout << ans << endl;

	return 0;
}

P5764 [CQOI2005] 新年好

题目链接：[CQOI2005] 新年好 – 洛谷

P5764 [CQOI2005] 新年好
//https://www.luogu.com.cn/problem/P5764

//求的是图里面的最短路径，而不是树里面的了
//要找的是最短顺序

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

const int N = 50005;
const int M = 2e5 + 5;

int head[N];//注意是无向边
int cnt;
int vis[N];//不是Dij里，而是dfs里的
int d[7][N];//存的是第i个亲戚到各点的最短距离
int rel[7];/*亲戚*/
int ans = 0x3f3f3f3f;

int n, m;

struct EDGE
{
	int v;
	int w;
	int next;
}EDGE[M * 2];

void add(int u, int v, int w)
{
	cnt++;
	EDGE[cnt].v = v;
	EDGE[cnt].w = w;
	EDGE[cnt].next = head[u];
	head[u] = cnt;
}

void Dij(int s)
{
	priority_queue<pair<int, int> >que;
	que.push({ 0, rel[s] });
	d[s][rel[s]] = 0;

	while (!que.empty())
	{
		int dis = -que.top().first;
		int dian = que.top().second;
		que.pop();

		if (dis != d[s][dian])
			continue;

		for (int j = head[dian]; j; j = EDGE[j].next)
		{
			int t = EDGE[j].v;
			int w = EDGE[j].w;
			if (d[s][t] > w + d[s][dian])
			{
				d[s][t] = w + d[s][dian];

				que.push({ -d[s][t], t });
			}
		}
		
	}
}

void dfs(int cur/*当前遍历亲戚个数*/, int cost/*到该点的距离*/, int pos/*当前亲戚*/)
{
	if (cost > ans)
		return;
	if (cur == 5)
	{
		ans = min(ans, cost);
		return;
	}
	for (int i = 1; i < 6/*是小于，不是等于，因为一开始就遍历了从家出发*/; i++)
	{
		if (vis[i] == 0)
		{
			vis[i] = 1;
			dfs(cur + 1/*遍历了的亲戚个数+1*/, cost + d[pos][rel[i]]/*加上当前亲戚到第i个亲戚的最短距离*/, i/*递归处理第i个亲戚*/);
			vis[i] = 0;
		}
	}
}

int main()
{
	quickio;
	cin >> n >> m;
	for (int i = 1; i <= 5; i++)
		cin >>rel[i];
	rel[6] = 1;
	int u, v, w;
	for (int i = 1; i <= m; i++)
	{
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}

	memset(d, 0x3f, sizeof(d));

	for (int i = 1; i <= 6; i++)
		Dij(i);

	memset(vis, 0, sizeof(vis));
	dfs(0, 0, 6);
	cout << ans << endl;
	return 0;
}

P2820 局域网

题目链接：局域网 – 洛谷

P2820 局域网
//https://www.luogu.com.cn/problem/P2820

//就是求最短路的变形

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

int n, k;

const int N = 105;
const int M = 10000000;

int d[N];
int ans;
int cnt;
int countx;
int head[N];
int vis[N];
int sum;

struct EDGE
{
	int v;
	int w;
	int next;
}EDGE[M * 2];

void add(int u, int v, int w)
{
	cnt++;
	EDGE[cnt].next = head[u];
	EDGE[cnt].v = v;
	EDGE[cnt].w = w;
	head[u] = cnt;
}

void prim(int s)
{
	priority_queue<pair<int, int> >que;
	que.push({ 0, s });
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;

	while (!que.empty())
	{
		int dis = -que.top().first;
		int dian = que.top().second;
		que.pop();

		if (dis != d[dian])
			continue;

		if (d[dian] != 0x3f3f3f3f)
			countx++;
		ans += d[dian];
		if (vis[dian] == 0)
		{
			vis[dian] = 1;

			for (int j = head[dian]; j; j = EDGE[j].next)
			{
				int t = EDGE[j].v;
				int w = EDGE[j].w;

				if (vis[t] == 0 && d[t] > w)
				{
					d[t] = w;
					que.push({ -d[t], t });
				}
			}
		}
	}
}

int main()
{
	cin >> n >> k;
	int u, v, w;
	int s;
	int minx = INT_MAX;
	while (k--)
	{
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);//注意也是无向
		sum += w;
		if (w != 0 && w < minx)
		{
			minx = w;
			s = u;/**/
		}
	}

	prim(s);/*不一定是1，而是取有最短路径的点*/

	cout << sum - ans << endl;
	return 0;
}

版权声明：本文为博主作者：脑子不好的小菜鸟原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/2301_79293429/article/details/137470924

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
心中带点小风骚的头像心中带点小风骚普通用户
0
上一篇 2024年4月16日
下一篇 2024年4月16日

相关推荐