赛前训练2-连通性系列问题——总结

发表于 更新于 分类于 ， ， ， 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 5 分钟

赛前训练2-连通性系列问题——总结

A

洛谷P2656

错误原因

double 的精度不够，应开 long double。

正解

  1. 条边只有在环上时，才可能多次经过，且一定会经过足够次直到边权为 00；
  2. 输入时维护 x[i],y[i],w[i],kw[i] 其中 kw[i] 表示第i涤边迭代经过的总边权和；
  3. 缩点建新DAG图，跑最长路。
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
#include<bits/stdc++.h>
typedef int int32;
#define int long long
#define double long double
using namespace std;
const int N = 8e4 + 5;
int n, m, s, dfn[N], low[N], scc[N], sum[N], num, cnt, ans;
vector<int>st;
bool vis[N];
struct node {
	int nxt, w, w1;
};
vector<node>nbr[N], new_nbr[N];
int work(int x, double y)
{
	int sum = 0;
	while (x)
		sum += x, x *= y;
	return sum;
}
void tarjan(int x)
{
	dfn[x] = low[x] = ++num, vis[x] = true;
	st.push_back(x);
	for (auto& y : nbr[x])
	{
		auto& nxt = y.nxt, & w = y.w, & w1 = y.w1;
		if (!dfn[nxt])
		{
			tarjan(nxt);
			low[x] = min(low[x], low[nxt]);
		}
		else if (vis[nxt])
			low[x] = min(low[x], dfn[nxt]);
	}
	if (dfn[x] == low[x])
	{
		cnt++;
		while (st.back() != x)
		{
			int tmp = st.back();
			st.pop_back();
			vis[tmp] = false;
			scc[tmp] = cnt;
		}
		st.pop_back();
		vis[x] = false;
		scc[x] = cnt;
	}
	return;
}
void dfs(int x, int sum)
{
	ans = max(ans, sum += ::sum[x]);
	for (auto& y : new_nbr[x])
	{
		auto& nxt = y.nxt, & w = y.w, & w1 = y.w1;
		dfs(nxt, sum + w);
	}
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		double u;
		cin >> x >> y >> z >> u;
		nbr[x].push_back({ y,z,work(z, u) });
	}
	cin >> s;
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(i);
	for (int i = 1; i <= n; i++)
		for (auto& y : nbr[i])
		{
			auto& nxt = y.nxt, & w = y.w, & w1 = y.w1;
			if (scc[i] != scc[nxt])
				new_nbr[scc[i]].push_back({ scc[nxt],w,w1 });
			else
				sum[scc[i]] += w1;
		}
	dfs(scc[s], 0);
	cout << ans;
	return 0;
}

B

CF1000E

思路

  • 跑求割边的 tarjan，再把每一个边双连通分量缩成一个点，最后求树的直径。
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
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 3e5 + 5;
int n, m, root, num, dfn[N], low[N], dcc[N], cnt, dis;
vector<pair<int,int>>nbr[N], new_nbr[N];
bool cut[N];
void tarjan(int x, int edge)
{
	dfn[x] = low[x] = ++num;
	for (auto& y : nbr[x])
	{
		auto& nxt = y.first, & w = y.second;
		if (!dfn[nxt])
		{
			tarjan(nxt, w);
			low[x] = min(low[x], low[nxt]);
			cut[w] |= low[nxt] > dfn[x];
		}
		else if (w != edge)
			low[x] = min(low[x], dfn[nxt]);
	}
	return;
}
void dfs(int x)
{
	dcc[x] = cnt;
	for (auto& y : nbr[x])
	{
		auto& nxt = y.first, w = y.second;
		if (!cut[w] && !dcc[nxt])
			dfs(nxt);
	} 
	return;
}
void dfs1(int x, int fa, int& to, int sum = 0)
{
	if (sum >= dis)
	{
		to = x;
		dis = sum;
	}
	for (auto& y : new_nbr[x])
	{
		auto& nxt = y.first, w = y.second;
		if (nxt != fa)
			dfs1(nxt, x, to, sum + 1);
	} 
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		nbr[x].push_back({ y,i });
		nbr[y].push_back({ x,i });
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			root = i, tarjan(i, 0);
	for (int i = 1; i <= n; i++)
		if (!dcc[i])
			cnt++, dfs(i);
	for (int i = 1; i <= n; i++)
		for (auto& y : nbr[i])
		{
			auto& nxt = y.first, w = y.second;
			if (dcc[i] != dcc[nxt])
				new_nbr[dcc[i]].push_back({ dcc[nxt],w });
		}
	int x = 0, y = 0;
	dfs1(1, 0, x);
	dis = 0;
	dfs1(x, 0, y);
	cout << dis;
	return 0;
}

C

CF1763E

错误原因

dp的状态转移方程写错了。

正解

  1. 有向图的点对只有三种关系：单向对、双向对、不连通；
  2. p可达图就是要构造恰好 pp 组点对是强连通的有向图；
  3. 给定 ii 个点，强连通的点对数介于 [0,i(i−1)2]\left[0,\frac{i(i-1)}{2}\right]；
  4. 要追求恰好 pp 组强连通点对，那么构造的图应该是若干 scc 的图；
  5. 把 scc 看作物品，把 size(size−1)2\frac{ {size} ({size}-1) } {2} 看作重量，把点数 size{size} 看作价值，问题转化为放满容量为 pp 的背包的最小价值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n, dp[N];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	dp[1] = 2;
	cin >> n;
	for (int i = 2; i <= n; i++)	
	{
		dp[i] = INT_MAX;
		for (int j = 2; ; j++)
			if (j * (j - 1) / 2 <= i)
				dp[i] = min(dp[i], j + dp[i - j * (j - 1) / 2]);
			else
				break;
	}
	cout << dp[n] << ' ' << dp[n] * (dp[n] - 1) / 2 - n;
	return 0;
}

D

CF1761E

错误原因

写了假解。

正解

  1. 选择点 xx 操作时，尽可能不要让 ×× 从原本的连通块分离；
  2. 当 xx 和所在连通块的每个都连了边时，xx才会分离；
  3. 只要是存在非完全图，那么就一定可以选出点 xx，使得至多操作 11 次完成任务；
  4. 而后分类讨论：
    • 本来连通：00 次；
    • 不连通
      • 只有完全图
        • 22 个完全图，每个操作等价于每次移动 11 个点到另一个完全图：min⁡(size1,size2)\min({size}_1,{size}_2)；
        • >2>2 个完全图：22 次
      • 存在非完全图：11 次。
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
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 4e3 + 5;
int t, n, in[N], fa[N], size[N], sum[N], cnt, tot;
char c[N][N];
vector<int>ans;
int find(int x)
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void unionn(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x != y)
	{
		fa[x] = y;
		::size[y] += ::size[x];
	}
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> t;
	while (t--)
	{
		cin >> n;
		ans.clear();
		cnt = tot = 0;
		for (int i = 1; i <= n; i++)
			fa[i] = i, ::size[i] = 1, sum[i] = 0;
		for (int i = 1; i <= n; i++)
		{
			in[i] = 0;
			for (int j = 1; j <= n; j++)
			{
				cin >> c[i][j];
				if (c[i][j] - '0')
				{
					in[i]++;
					unionn(i, j);
				}
			}
		}
		for (int i = 1; i <= n; i++)
			if (in[i] == ::size[find(i)] - 1)
				sum[find(i)]++;
		for (int i = 1; i <= n; i++)
			if (fa[i] == i)
				if (sum[i] == ::size[i] && ::size[i] > 1)
					cnt++;
				else
					tot++;
		if (cnt + tot == 1)
		{
			cout << "0\n";
			continue;
		}
		if (tot)
		{
			int pos = 0;
			for (int i = 1; i <= n; i++)
				if (in[i] < ::size[find(i)] - 1 || !in[i])
					if (n - in[i] > n - in[pos] || !pos)
						pos = i;
			ans.push_back(pos);
		}
		else if (cnt == 2)
		{
			int pos = 1;
			for (int i = 2; i <= n; i++)
				if (sum[find(i)] < sum[find(pos)])
					pos = find(i);
			for (int i = 1; i <= n; i++)
				if (find(pos) == find(i))
					ans.push_back(i);
		}
		else
		{
			int pos = 1;
			ans.push_back(1);
			for (int i = 1; i <= n; i++)
				if (find(i) != find(pos))
				{
					ans.push_back(i);
					break;
				}
		}
		cout << ans.size() << '\n';
		for (auto& x : ans)
			cout << x << ' ';
		cout << '\n';
	}
	return 0;
}