「Solution」图论100题 1~5题

Posted on Edited on In

前言

咕咕咕了这么久，居然更新了。。。
因为本人太菜了，所以掺了点并查集的题凑合。
总之这个帖子又复活了。

T1 「NOIP2015」信息传递

link
题意很清晰了，可以直接用$dfs$找一个最小环。
在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
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 2 * 1e6 + 5;
const int INF = 0x3f3f3f3f;

int n, ans, t[MAXN], de[MAXN], num[MAXN], tot;
bool vis[MAXN];

void dfs(int u, int d) {
	de[u] = d;
	num[u] = tot;
	if (de[t[u]] != 0) {
		if (num[t[u]] < tot) return ;
		ans = min(ans, d - de[t[u]] + 1);
	} else dfs(t[u], d + 1);
} 

int main() {
	ans = INF;
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf ("%d", &t[i]);
	}
	for (int i = 1; i <= n; i++) {
		if (de[i] == 0) {
			tot++;
			dfs(i, 1);
		}
	}
	printf ("%d\n", ans);
	return 0;
}

T2 「NOIP2009」最优贸易

link

step1

首先，他可以在图上到处走动，所以很自然地可以建一张图，所有的边权都是0。
然后这道题只与水晶球的价格有关，所以我们把点权搬到边权上面。

step2

因为他只进行一次买卖，所以有下面两种情况：
假设从$u$到$v$，水晶球在$u$的价格为$w$.
1.买. 建第二层图，连接第一层图 -> 在$u$和$v$之间建一条边边权为$-w$。
2.卖. 建第三层图，连接第二层图 -> 在$u$和$v$之间建一条边边权为$w$。

step3

我们在最后有两种方法走向终点：

不买卖直接走向终点

直接在第一层图的n号节点建立边权为0的有向边接入一个“大终点”

买卖一次后走向终点

在第三层图的n号节点建立边权为0的有向边接入“大终点”

至此，这道题就只需要求一个最长路即可。

Code

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
90
91
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100005 * 3 + 1;

int n, m, a[MAXN];
bool vis[MAXN];
int dis[MAXN];
queue<int> q;

void read(int& x) {
	x = 0;
	int f = 1;
	char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') f = -f;
		c = getchar();
	}
	while (c <= '9' && c >= '0') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	x *= f;
}

struct edge {
	int v, w;
	edge(){}
	edge(int V, int W) {
		v = V;
		w = W;
	}
};
vector<edge> G[MAXN];

void AddEdge(int u, int v, int w) {
	G[u + n * 0].push_back(edge(v + n * 0, 0));
	G[u + n * 1].push_back(edge(v + n * 1, 0));
	G[u + n * 2].push_back(edge(v + n * 2, 0));
	G[u + n * 0].push_back(edge(v + n * 1, -w));
	G[u + n * 1].push_back(edge(v + n * 2, w));
}

void Spfa() {
	memset(vis, 0, sizeof(vis));
	memset(dis, 0xcf, sizeof(dis));
	dis[1] = 0;
	vis[1] = 1;
	q.push(1);
	while (q.size()) {
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i].v, w = G[u][i].w;
			if (dis[v] < dis[u] + w) {
				dis[v] = dis[u] + w;
				if (vis[v] == 0) {
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
	printf ("%d\n", dis[n]);
}

int main() {
	read(n);
	read(m);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
	}
	for (int i = 1, u, v, opt; i <= m; i++) {
		read(u), read(v), read(opt);
		AddEdge(u, v, a[u]);
		if (opt == 2) {
			AddEdge(v, u, a[v]);
		}
	}
	G[n].push_back(edge(n * 3 + 1, 0));
	G[n * 3].push_back(edge(n * 3 + 1, 0));
	n *= 3;
	n++;
	Spfa();
	return 0;
}

T3「Uva 10004」二染色

做了四色问题后调的一道题。
又是$dfs$，提前给0节点涂上-1，然后在每次处理时判断两个地方。
1.如果没访问，就去递归，每次都涂上相反的颜色。
2.如果访问过，并且涂上了现在相同的颜色，直接返回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
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 205; 

int n, m, p[MAXN];
vector<int> G[MAXN];

bool dfs(int u, int last) {
	p[u] = -last;
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (p[v] != 0 && p[v] == p[u]) return false;
		if (p[v] == 0 && dfs(v, p[u]) == 0) return false;
	}
	return true;
}

int main() { 
	while (scanf ("%d", &n), n) {
		scanf ("%d", &m);
		for (int i = 1; i <= n; i++) G[i].clear();
		for (int i = 1, u, v; i <= m; i++) {
			scanf ("%d %d", &u, &v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		memset(p, 0, sizeof(p));
		if (dfs(0, -1)) printf ("BICOLORABLE\n");
		else printf ("NOT BICOLORABLE\n");
	}
	return 0;
}

T4巡逻

这道题就有点意思了，但我的做法不是最优的。
如果想找到更好的解法，可以问问lifan。
在这里有两种情况：

1.k = 1

比较显然，当在没有修路的时候，按照dfs的顺序(访问和回溯)应该将每条边访问两遍。
假设我们在$u$和$v$之间建一条边，那么在$u$到$v$的唯一路径上的所有道路都只用访问一边，即将$2\times(n - 1)$条边变成了$2 \times (n - 1)-Lenth_{(u,v)}$。
那么要是删掉的边最多，可以直接想到，求出直径，然后将它删掉。

2.k = 2

这种情况就有点难想了。
那么在求出最长边后(直径)，在求出次长边即可，可是当两条边重合时需要将重合的边加上，即警察会将每条边访问一次。
求两条边的重合部分写出来很麻烦，有没有更简单的方法呢?
可以回到式子上：
$2 \times (n - 1)-Lenth_1-Lenth_2+Lenth_3$，$Lenth_3$即为两边的重合边。
可以想到：
$2 \times (n - 1)-Lenth_1-Lenth_2+Lenth_3 = 2 \times (n - 1)-Lenth_1-(Lenth_2-Lenth_3)$。
来到这一步其实已经很清晰了。
可以在求完直径时，把直径上的边全部取反成-1,那么再求次长边时就可以直接减去此长度。

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
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;

int n, l1, l2, far, k, d[MAXN], pre[MAXN], last, way[MAXN], cnt;
vector<int> G[MAXN];
bool vis[MAXN];
map<pair<int, int>, bool> add;

void dfs(int& tmp, int u, int fa) {
    if (tmp < d[u]) {
        tmp = d[u];
        last = u;
        far = u;
    }
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == fa)
            continue;
        d[v] = d[u] + 1;
        pre[v] = u;
        dfs(tmp, v, u);
    }
}

void dpdfs(int u) {
    vis[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (vis[v] == 0) {
            dpdfs(v);
            int w = 1;
            if (add[make_pair(u, v)] == 1 || add[make_pair(v, u)] == 1)
                w = -1;
            l2 = max(l2, d[u] + d[v] + w);
            d[u] = max(d[u], d[v] + w);
        }
    }
}

void print(int p) {
    if (pre[p] == 0) {
        way[++cnt] = p;
        return;
    }
    print(pre[p]);
    way[++cnt] = p;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(l1, 1, 0);
    d[far] = 0;
    memset(pre, 0, sizeof(pre));
    dfs(l1, far, 0);
    if (k == 1) {
        printf("%d\n", (n - 1) * 2 - (l1 - 1));
        return 0;
    } else {
        print(last);
        for (int i = 1; i <= cnt; i++) {
            add[make_pair(way[i], way[i + 1])] = 1;
        }
        memset(d, 0, sizeof(d));
        dpdfs(1);
        printf("%d\n", (n - 1) * 2 - (l1 - 1) - (l2 - 1));
    }
    return 0;
}

T5 「CF9E」Interesting Graph and Apples

link
这是OJ上为数不多的能看清题面的CF的题。
我还是简单翻译一下吧。
题意：在$n$个点$m$条边的图上添加最少的边，使其成为一个大环。
水入并查集，再添加两条边的时候，可以将他们加入一个集合里。并更新度。
如果其中有点的入度$>2$那么输出$NO$，因为在一个环中，每个节点的度至多为2，且此题不能删边，可以直接结束。
然后依次选择两个节点，如果它们的度都小于2，并且没有在一个集合中，就可以把它们加在一起，然后更新度数。
在加边完成之后，会出现总边只有$n-1$的情况，此时找到剩下两个度为1的点，把它们连在一起即可。

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
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 55;

int n, m;
int deg[MAXN], fa[MAXN];

void MakeSet(int n) {
	for (int i = 1; i <= n; i++) fa[i] = i;
}

int FindSet(int v) {
	if (fa[v] == v) return v;
	else return fa[v] = FindSet(fa[v]);
}

void UnionSet(int u, int v) {
	int x = FindSet(u);
	int y = FindSet(v);
	if (x == y) return;
	fa[x] = fa[y];
	return;
}

struct node {
	int u, v;
	node(){}
	node(int U, int V) {
		u = U;
		v = V;
	}
};
vector<node> ans;

int main() {
	scanf ("%d %d", &n, &m);
	MakeSet(n);
	for (int i = 1, u, v; i <= m; i++) {
		scanf ("%d %d", &u, &v);
		deg[u]++, deg[v]++;
		UnionSet(u, v);
	}
	for (int i = 1; i <= n; i++) if (deg[i] > 2) {
		printf ("NO\n");
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) if (FindSet(i) != FindSet(j) && deg[i] < 2 && deg[j] < 2) {
			ans.push_back(node(i, j));
			deg[i]++, deg[j]++;
			UnionSet(i, j); 
		}
	}
	if (ans.size() + m == n - 1) {
		int u = 0, v = 0; 
		for (int i = 1; i <= n; i++) {
			if (deg[i] < 2) {
				deg[i]++;
				if (u == 0) u = i;
				else v = i;
			}
		}
		ans.push_back(node(u, v));
	}
	for (int i = 1; i <= n; i++) {
		if (FindSet(i) != FindSet(1)) {
			printf ("NO\n");
			return 0;
		}
	}
	printf ("YES\n%d\n", ans.size());
	for (int i = 0; i < ans.size(); i++) {
		node now = ans[i];
		printf ("%d %d\n", now.u, now.v);
	}
	return 0;
}

The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」