图论刷题记录

发表于 更新于 分类于 本文字数： 5.5k 阅读时长 ≈ 5 分钟
  • 图的遍历
  • 最短路算法
  • 最小生成树

图的遍历

洛谷P2661（并查集求有向图最小环）

也放在并查集那一章里了，装作刷题很多的样子

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
75
//图论最小环问题, 并查集
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAX_N = 2e5 + 2;

int par[MAX_N];
int d[MAX_N];

int n;
int ans = 2e9;

void init()
{
    for(int i = 0; i <= n; ++i)
    {
        par[i] = i;
        d[i] = 0;
    }
}

int find(int x) //查询根节点并更新距离
{
    if(x == par[x])
        return x;
    else
    {
        int last= par[x];
        par[x] = find(par[x]); //查找途中，把每个点都连向根节点
        d[x] += d[last];
    }
    return par[x];
}

bool same(int x, int y)
{
    return find(x) == find(y);
}

void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return ;
    else
        par[x] = y; //x连到y上
}

void solve(int a, int b)
{
    int x = find(a);
    int y = find(b);
    if(x == y)
        ans = min(ans, d[a] + d[b] + 1); //环的大小为两边离根节点的距离加上两点距离（即1）
    else
    {
        unite(x, y);
        d[a] = d[b] + 1;
    }
}

int main()
{
    scanf("%d", &n);
    init();
    for(int i = 1; i <= n; ++i)
    {
        int t;
        scanf("%d", &t);
        solve(i, t);
    }
    printf("%d\n", ans);
    return 0;
}

洛谷P1330（染色+bfs求连通块数量+思路）

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<cstdio>
#include<queue>
using namespace std;

const int MAX_N = 1e4 + 1;
const int MAX_M = 1e5 + 1;

bool maze[MAX_N][MAX_N];
int d[MAX_N];
int used[MAX_N];
int n, m;
int res1 = 0;
int res2 = 0;
int ans = 0;
int possiable = 1;

queue<int> que;

void bfs(int x)
{
    que.push(x); //压入该顶点
    d[x] = 0;
    while(!que.empty())
    {
        int t = que.front();
        que.pop();
        //printf("%d ", t);
        for(int i = 1; i <= n; ++i)
        {
            if(maze[t][i]) //如果t和i之间有边
            {
                if(d[i] == -1)
                {
                    d[i] = !d[t];
                    que.push(i);
                }
                else
                {
                    if(d[t] == d[i])
                    {
                        possiable = 0;
                        return ;
                    }
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) //初始化，未访问
        d[i] = -1;
    for(int i = 1; i <= m; ++i) //初始化图
    {
        int a, b;
        scanf("%d%d", &a, &b);
        maze[a][b] = maze[b][a] = 1;
    }
    for(int i = 1; i <= n; ++i)
    {
        if(d[i] == -1) //如果未访问过该顶点，遍历这个连通块
        {
            possiable = 1;
            res1 = 0;
            res2 = 0;
            bfs(i);
            if(!possiable) //如果不可能，输出-1，结束程序
            {
                printf("Impossible\n");
                return 0;
            }
            for(int i = 1; i <= n; ++i) //每个连通块的最少河蟹数
            {
                if(d[i] == -1 || used[i])
                    continue;
                if(d[i] == 1)
                    res1++;
                else if(!d[i])
                    res2++;
                used[i] = 1;
            }
            ans += min(res1, res2);
        }
    }
    printf("%d\n", ans);
    return 0;
}

洛谷P1341（欧拉回路问题+并查集）

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
75
76
77
78
79
80
81
82
83
84
85
86
//欧拉回路问题
//并查集
#include<cstdio>

int n;
int par[130];
int deg[130];
int G[130][130];
char ans[1500];
char a[3];
int head = 0;

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

void euler(int u)
{
    for(int v = 64; v <= 125; ++v)
        if(G[u][v])
        {
            G[u][v] = G[v][u] = 0;
            euler(v);
        }
    ans[n--] = u;
}

int main()
{
    scanf("%d", &n);
    for(int i = 64; i <= 125; i++)
        par[i] = i;
    for(int i = 1; i <= n; i++)
    {
        scanf("%s", a);
        G[a[0]][a[1]] = G[a[1]][a[0]] = 1;
        deg[a[0]]++;
        deg[a[1]]++;
        int x = find(a[0]);
        int y = find(a[1]);
        par[x] = y; //并查集连起来
    }

    int cnt = 0;
    for(int i = 64; i <= 125; i++) //若不连通
        if(par[i] == i && deg[i])
            cnt++;
    if(cnt > 1)
    {
        printf("No Solution\n");
        return 0;
    }

    cnt = 0;
    head = 0;

    for(int i = 64; i <= 125; i++) //奇数度结点个数
    {
        if(deg[i] & 1)
        {
            cnt++;
            if(!head) head = i;
        }
    }

    if(cnt && cnt != 2)
    {
        printf("No Solution\n");
        return 0;
    }

    if(!head)//如果是欧拉回路
        for(int i = 64; i <= 125; i++)
            if(deg[i])
            {
                head = i;
                break;
            }
    euler(head);
    printf("%s\n", ans);
    return 0;
}

洛谷P2921（有向图成环+步数）

大概是照着题解默了一遍，早上9：00写到14：30不带停的，还是实现不了，实在饿得受不了就偷懒了~

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
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAX_N = 1e5 + 1;

int n;
int G[MAX_N];
int color[MAX_N];
int sizec[MAX_N];
int sucdfn[MAX_N];
int dfn[MAX_N];

void init()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &G[i]);
    }
}

void solve()
{
    for(int cow = 1; cow <= n; ++cow)
    {
        for(int i = cow, cnt = 0; ; i = G[i], ++cnt)
        {
            if(!color[i])
            {
                color[i] = cow;
                dfn[i] = cnt;
            }
            else if(color[i] == cow)
            {
                sizec[cow] = cnt - dfn[i];
                sucdfn[cow] = dfn[i];
                printf("%d\n", cnt);
                break;
            }
            else
            {
                sizec[cow] = sizec[color[i]];
                sucdfn[cow] = cnt + max(sucdfn[color[i]] - dfn[i], 0);
                printf("%d\n", sucdfn[cow] + sizec[cow]);
                break;
            }
        }
    }
}

int main()
{
    init();
    solve();
    return 0;
}

最短路算法

洛谷P1339（Dijistra板子题）

我不会说我板子题都WA、RE了的

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
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAX_C = 2501;
const int MAX_T = 6201;
const int INF = 1e9;

int C, T, Ts, Te;
int cost[MAX_T][MAX_T];
int dis[MAX_T];
int vis[MAX_T];

void init()
{
    scanf("%d%d%d%d", &T, &C, &Ts, &Te);
    for(int i = 1; i <= T; ++i)
    {
        for(int j = 1; j <= T; ++j)
        {
            cost[i][j] = INF;
        }
        dis[i] = INF;
        vis[i] = false;
    }

    for(int i = 1; i <= C; ++i)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        cost[a][b] = cost[b][a] = c;
    }

    for(int i = 1; i <= T; ++i)
        dis[i] = cost[Ts][i];
    dis[Ts] = 0; //起点初始化
    vis[Ts] = 1; //起点初始化
}

void Dijistra()
{
    for(int i = 1; i <= T; ++i)
    {
        int x, m = INF;
        for(int y = 1; y <= T; ++y) //找到最小的边x
            if(!vis[y] && dis[y] <= m)
                m = dis[x = y];
        vis[x] = 1;
        for(int y = 1; y <= T; ++y) //利用x来松弛
            dis[y] = min(dis[y], dis[x] + cost[x][y]);
    }
}

int main()
{
    init();
    Dijistra();
    printf("%d\n", dis[Te]);
    return 0;
}