《图》相关刷题

A - 拓扑排序 / 家谱树
//https://vjudge.net/contest/613618#problem/A

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 租用游艇
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
// //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;
}

最短路计数
//最短路计数
//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;
}

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

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

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. 岛屿数量
//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;
    }
};

//广搜：用队列，有模板：最短路径模板
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. 岛屿的最大面积
//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
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 灾后重建
注意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 邮递员送信
建反图，注意要将各个数组开为平时写的两倍，否则存不下
//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*/
//反向建图

//按题中给的示例：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;
}