第十七节 图论 - 2
AT_tenka1_2015_qualB_b 题解
洛谷链接&Atcoder 链接
本篇题解为此题较简单做法及较少码量，并且码风优良，请放心阅读。
题目简述
给定一个集合形式，判断此集合是 dict 还是 set。
思路
简单的模拟题。
首先需要特判 {} 的情况，应直接输出 dict。
接着观察两个集合的特征，很容易即可发现 dict 和 set 的最明显的区别就是一个有 : 一个没有，而我们需要注意 expr 可是任何集合或者数字，所以有可能出现 {1,{2:3}} 的情况，而这种情况就不能直接看有无冒号进行判断了。
我们需要用 \(num\) 来记录当前是第几层括号，如果在第一层括号中发现了冒号，那么这个集合就是 dict 了，反之就是 set。
经过以上分析，很容易即可写出代码了：
#include<iostream>
using namespace std;
string str;
int main() {
cin >> str;
// 特判 {} 的情况
if(str.length() == 2) {
cout << "dict\n";
return 0;
}
int num = 0; // num 记录层数
for(int i = 0; i <= str.length(); i ++) {
if(str[i] == '{') num ++; // 遇到 { 层数加 1
if(str[i] == '}') num --; // 遇到 } 层数减 1
if(str[i] == ':' && num == 1) {
cout << "dict\n"; // 最外层遇到 ：
return 0;
}
}
cout << "set\n"; // 换行好习惯
return 0;
}
提交记录
CF709B 题解
洛谷链接&CF 链接
本篇题解为此题较简单做法及较少码量，并且码风优良，请放心阅读。
题目简述
给定 \(N\) 个点，在一条数轴上，位置为 \(x_1,…,x_n\)，你的位置为 \(p\)，你要经过 \(N-1\) 个点，求至少要走的距离。
思路
首先因为输入是乱序的，所以需要由小到大排序。
又因为需要经过 \(N-1\) 个点，所以要么不走左端点，要么不走右端点，这样分两种情况讨论，分别求出答案取 \(\min\) 即可。
首先分析情况 \(1\)，要么 \(p \le a_2 \le a_n\)，要么 \(a_2 \le p \le a_n\)，要么 \(a_2 \le a_n \le p\)，第二种不论先去 \(a_2\) 还是 \(a_n\) 结果都一样。所以不讨论，第一三种需要讨论一下，对于第一种一定是先去 \(a_2\) 结果最小， 对于第三种一定是先去 \(a_n\) 结果最小，只需对这两种分别处理最后取 \(\min\) 即可，由此分析可得这种情况的方程式为：
同样分析可得情况 \(2\) 的方程式：
最后对两种情况取 \(\min\) 即可。
经过以上分析，很容易即可得出代码了：
#include<iostream>
#include<algorithm>
using namespace std;
int n, a[100005], p;
long long ans = 0x3f3f3f3f; // 要取 min 所以需初始化一个较大数
int min(int x, int y) { return (x < y) ? x : y; }
int abs(int x) { return (x > 0) ? x : -x; }
int main(){
cin >> n >> p;
if(n == 1) { cout << "0\n"; return 0; } // 特判
for(int i = 1; i <= n; i ++) cin >> a[i];
sort(a + 1, a + n + 1); // 因为是乱序，所以需要排序
long long num1 = 0, num2 = 0; // 可不开 long long
// 情况 1
num1 = min(abs(a[n] - p) + abs(a[n] - a[2]), abs(a[2] - p) + abs(a[n] - a[2]));
// 情况 2
num2 = min(abs(a[n - 1] - p) + abs(a[n - 1] - a[1]), abs(a[1] - p) + abs(a[n - 1] - a[1]));
ans = min(num1, num2); // 答案取 min
cout << ans << endl; // 输出，换行好习惯
return 0;
}
提交记录：
A. 小埋学习图之图的遍历
时间：1s 空间：512M
题目描述
小埋最近在学习有向图的遍历相关知识，小埋学习过图的遍历的相关方法，可以使用 \(\text{dfs}\) 或者 \(\text{bfs}\) 来遍历整个有向图，但是小埋发现这个问题有一些不一样，这个图的遍历是问你当前点能够到达的点的最大编号，小埋希望你能帮她解决这个问题。
输入格式
第一行两个整数一个 \(n\) 一个 \(m\)，\(n\) 代表有向图中有 \(n\) 个点，\(m\) 代表有向图中有 \(m\) 条有向边。
接下来是 \(m\) 条边。
输出格式
输出每个点能够到达的最大编号
样例1输入
4 3
1 2
1 3
2 3
样例1输出
3 3 3 4
数据范围
\(1 \le n,m \le 100000\)
点击查看代码
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;
int n, m, fr, to;
int vis[100005];
vector<int> v[100005];
void dfs(int x, int y) {
for (int i = 0; i < v[x].size(); i ++) {
if(vis[v[x][i]]) continue;
vis[v[x][i]] = y;
dfs(v[x][i], y);
}
return;
}
int main() {
scanf("%d %d", &n, &m);
while (m --) {
scanf("%d %d", &fr, &to);
v[to].push_back(fr);
}
for (int i = n; i >= 1; i --)
if (!vis[i]) vis[i] = i, dfs(i, i);
for (int i = 1; i <= n; i ++) printf("%d ", vis[i]);
return 0;
}
编译结果
compiled successfully
time: 328ms, memory: 8272kb, score: 100, status: Accepted
> test 1: time: 0ms, memory: 5976kb, points: 10, status: Accepted
> test 2: time: 39ms, memory: 8168kb, points: 10, status: Accepted
> test 3: time: 38ms, memory: 8008kb, points: 10, status: Accepted
> test 4: time: 24ms, memory: 7392kb, points: 10, status: Accepted
> test 5: time: 40ms, memory: 8272kb, points: 10, status: Accepted
> test 6: time: 30ms, memory: 7500kb, points: 10, status: Accepted
> test 7: time: 40ms, memory: 8220kb, points: 10, status: Accepted
> test 8: time: 35ms, memory: 7924kb, points: 10, status: Accepted
> test 9: time: 36ms, memory: 8112kb, points: 10, status: Accepted
> test 10: time: 46ms, memory: 8252kb, points: 10, status: Accepted
B. 小埋学习图之环问题
时间：1s 空间：512M
题目描述
小埋最近在学习图相关知识，平时做的一些题目都是没有环的情况，现在小埋遇到了一个关于图的环的问题，
问题描述是有一个含 \(n\) 个顶点的双向图，每对顶点最多通过一条边连接，让小埋找到图中的最短的环的长度，
如果不存在环的话，就输出 -1。
环是指以同一节点开始和结束，并且路径中的每条边仅使用一次。
题目输入
第一行是两个整数 \(n，m\)，\(n\) 代表该图有 \(n\)个节点，\(m\) 的话代表有 \(m\) 条双向边。
题目输出
输出一个整数是该图中的最小环的长度。
样例1输入
7 7
1 2
2 3
3 1
4 5
5 6
6 7
7 4
样例1输出
3
样例2输入
3 2
1 2
2 3
样例2输出
-1
数据范围
\(2 \le n \le 1000\)，\(1 \le m \le 1000\)，\(1 \le u,v \le n\)，\(u \ne v\)
不存在重复的边
点击查看代码
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;
int n, m, ans = 0x3f3f3f3f;
int vis[1005];
vector<int> v[1005];
void bfs(int x) {
memset(vis, 0, sizeof vis);
queue<int> q;
q.push(x);
q.push(0);
while(!q.empty()) {
int u, f;
u = q.front(); q.pop();
f = q.front(); q.pop();
for(int i = 0; i < v[u].size(); i ++) {
if(v[u][i] != f) {
if(vis[v[u][i]] != 0 && vis[v[u][i]] + vis[u] + 1 != 2 && vis[v[u][i]] + vis[u] + 1 <= n)
ans = min(ans, vis[v[u][i]] + vis[u] + 1);
else {
vis[v[u][i]] = vis[u] + 1;
q.push(v[u][i]);
q.push(u);
}
}
}
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; i ++) {
int fr, to;
cin >> fr >> to;
v[fr].push_back(to);
v[to].push_back(fr);
}
for(int i = 1; i <= n; i ++) {
//memset(vis, 0, sizeof vis);
bfs(i);
}
if(ans == 0x3f3f3f3f) cout << "-1\n";
else cout << ans << endl;
return 0;
}
编译结果
compiled successfully
time: 92ms, memory: 3536kb, score: 100, status: Accepted
> test 1: time: 6ms, memory: 3340kb, points: 10, status: Accepted
> test 2: time: 2ms, memory: 3464kb, points: 10, status: Accepted
> test 3: time: 18ms, memory: 3448kb, points: 10, status: Accepted
> test 4: time: 8ms, memory: 3472kb, points: 10, status: Accepted
> test 5: time: 11ms, memory: 3424kb, points: 10, status: Accepted
> test 6: time: 0ms, memory: 3536kb, points: 10, status: Accepted
> test 7: time: 12ms, memory: 3432kb, points: 10, status: Accepted
> test 8: time: 7ms, memory: 3480kb, points: 10, status: Accepted
> test 9: time: 13ms, memory: 3384kb, points: 10, status: Accepted
> test 10: time: 15ms, memory: 3472kb, points: 10, status: Accepted
C. 小埋学习图之无法到达的点关系问题
时间：1s 空间：512M
题目描述
小埋最近在学习关于图相关的一些知识，现在小埋遇到了这样一个问题，给我们一个整数 \(n\)，
表示一张无向图中有 \(n\) 个节点，编号为 \(1 \sim n\)。然后输入一个 \(m\)，然后有 \(m\) 条双向边，每次输入两个整数
\(u，v\) 代表 \(u，v\) 之间有一条双向边，现在想要知道所有无法互相到达的不同的点对数目。
无法互相到达的意思是，\(a\) 点不能到达 \(b\) 点，\(b\) 不能到达 \(a\)点。
题目输入
输入一行有两个整数 \(n，m\)
以下 \(m\) 行，每行两个整数，\(u，v\) 两条边。
题目输出
输出一个整数，代表相互不能到达的点对数。
样例1输入
3 3
1 2
2 3
1 3
样例1输出
0
样例2输入
7 5
1 3
1 6
3 5
2 7
6 5
样例2输出
14
数据范围
\(1 \le n \le 100000\),\(1 \le m \le 50000\)。
不会有重复边
样例二的图如下。
点击查看代码
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string.h>
#include<map>
using namespace std;
long long n, m, num[100005], ans = 0, cnt = 0;
bool vis[100005];
vector<int> v[100005];
void dfs(int t, int x) {
vis[x] = true;
for(int i = 0; i < v[x].size(); i ++) {
if(vis[v[x][i]]) continue;
num[t]++;
dfs(t, v[x][i]);
}
return;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; i ++) {
int fr, to;
cin >> fr >> to;
v[fr].push_back(to);
v[to].push_back(fr);
}
for(int i = 1; i <= n; i ++) {
if(!vis[i]) {
num[cnt + 1] = 1;
dfs(++cnt, i);
}
}
for(int i = 1; i <= cnt; i ++) {
ans += num[i] * (n - num[i]);
}
cout << ans / 2 << endl;
return 0;
}
编译结果
compiled successfully
time: 239ms, memory: 8140kb, score: 100, status: Accepted
> test 1: time: 28ms, memory: 8008kb, points: 10, status: Accepted
> test 2: time: 18ms, memory: 7184kb, points: 10, status: Accepted
> test 3: time: 34ms, memory: 8140kb, points: 10, status: Accepted
> test 4: time: 35ms, memory: 8048kb, points: 10, status: Accepted
> test 5: time: 2ms, memory: 5788kb, points: 10, status: Accepted
> test 6: time: 19ms, memory: 6928kb, points: 10, status: Accepted
> test 7: time: 35ms, memory: 7500kb, points: 10, status: Accepted
> test 8: time: 17ms, memory: 7084kb, points: 10, status: Accepted
> test 9: time: 22ms, memory: 7408kb, points: 10, status: Accepted
> test 10: time: 29ms, memory: 8052kb, points: 10, status: Accepted