如何部署thinkphp网站,网站开发建设计入什么科目,北京微网站建设,商城系统网站建设开发4979. 合适的环 - AcWing题库 给定一个 n 个点 m 条边的无向图。 图中不含重边和自环。 请你在图中选出一个由三个点组成的环。 设图中一共有 x 条边满足#xff1a;不在选择的环内#xff0c;且与选择的环内某个点相连。 我们希望通过合理选环#xff0c;使得 x 的值尽可能…
4979. 合适的环 - AcWing题库 给定一个 n 个点 m 条边的无向图。 图中不含重边和自环。 请你在图中选出一个由三个点组成的环。 设图中一共有 x 条边满足不在选择的环内且与选择的环内某个点相连。 我们希望通过合理选环使得 x 的值尽可能小。 请你输出 x 的最小可能值。 输入格式 第一行包含两个整数 n,m。 接下来 m 行每行包含两个整数 a,b表示点 a和点 b 之间存在一条无向边。 输出格式 如果存在满足条件的环则输出 x 的最小可能值。 否则输出 -1。 数据范围 前 33 个测试点满足 3≤n≤100≤m≤10。 所有测试点满足 3≤n≤40000≤m≤40001≤a,b≤na≠。 输入样例1 5 6
1 2
1 3
2 3
2 4
3 4
4 5输出样例1 2样例1解释 给定图中由三个点组成的环一共有两个分别为点 1,2,3 组成的环以及点 2,3,4 组成的环。 对于点 1,2,3 组成的环我们逐个分析每条边是否满足不在环内且与环内的某个点相连。 边 (1,2) 在环内。边 (1,3 在环内。边 (2,3)在环内。边 (2,4)不在环内且与点 2 相连。边 (3,4)不在环内且与点 3 相连。边 (4,5)不在环内但是与点 1,2,3 均不相连。 因此如果选择点 1,2,3组成的环则 x 的值为 2。 对于点 2,3,4 组成的环我们逐个分析每条边是否满足不在环内且与环内的某个点相连。 边 (1,2) 不在环内且与点 2 相连。边 (1,3)不在环内且与点 3 相连。边 (2,3)在环内。边 (2,4) 在环内。边 (3,4) 在环内。边 (4,5) 不在环内且与点 4 相连。 因此如果选择点 2,3,4组成的环则 x 的值为 3。 综上x 的最小可能值为 2。 输入样例2 7 4
2 1
3 6
5 1
1 7输出样例2 -1 图论问题x 的表示选取的三个点各自和其他点连接成的线的数量之和每个点排除共同形成环的另外两个点 通过二维数组 arr[i][j]存储点表示点 i 和点 j 之间存在一条线结构体 s[i]{a,b} 存储线表示 第 i 条线由点 a 和 点 b 相连mp[i] 存储第 i 个点和几个点相连 根据题意外循环遍历线1-m可通过 s 得到连接线的两个点 ab内循环遍历第三个点 c通过 arr 判断三个点之间是否都存在线形成环然后通过 mp 得到 x因为 mp 存储的点 i 连接的其他所有点数量但 x 求的是形成环的三个点分别排除与另外两点之间的线的情况所以三个点每个点排除两条三个点排除 6 条一共就是 6 条就是 -6. AC code #includebits/stdc.h
using namespace std;
int arr[4010][4010];
int n, m;
struct s {int a, b;
} s[4010];
unordered_mapint, int mp;
int main() {cin n m;for (int i 1; i m; i) {int a, b;cin a b;s[i] {a, b};arr[a][b];arr[b][a];mp[a], mp[b];}int ans 2e9;for (int i 1; i m; i) {int a s[i].a, b s[i].b;
// cout a bendl;for (int c 1; c n; c) {if (arr[a][c] arr[b][c]) {int res mp[a] mp[b] mp[c] - 6;ans min(res, ans);}}}if (ans ! 2e9) {cout ans;} else cout -1;}
