图论刷题记录

  • 图的遍历
  • 最短路算法
  • 最小生成树

图的遍历

洛谷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;
}
0%