CF117C Cycle 解题报告_综合

CF117C Cycle 解题报告

1 题目链接

https://codeforces.com/problemset/problem/117/C

2 题目整理

题目：循环

题目描述

竞赛图是一个没有自环的有向图，其中每一对顶点都由一个有向边连接。也就是说，对于任何两个顶点u和v ( u ?≠? v )，要么存在从u到v的边，要么存在从v到u的边。

给你一个由n 个顶点组成的竞赛图。你的任务是找到一个长度为 3 的循环。

输入格式

第一行包含一个整数n. 接下来的n行包含图的邻接矩阵a（无空格）。如果有一条从顶点i到顶点j的边，则 $a_{i,j} = 1$ 否则 $a_{i,?j}?=?0$ .其中，(i,j)代表第i行中的第j个字符。

可以保证给定的图是一个竞赛图，即 $a_{i,i}?=?0$ ,且?? $a_{i,j} \neq a_{j,i}?$ 。

输出格式

打印 $x_1、x_2、x_3$ 三个不同顶点，这样 $a_{x_1,x_2}?=? a_{x_2,x_3} = ?a_{x_3,x_1} =?1$ 。如果长度等于3的循环不存在，打印"-1"。

如果有多种解决方案，请打印其中任何一种。

样例输入1

样例输出1

1 3 2

样例输入2

样例输出2

-1

数据范围

对于 $100\%$ 的数据:

$\le n \le 5000$

3 题意分析

3.1 题目大意

给定一个竞赛图，请打印出其中的一个大小为三的环。

3.2 样例分析

如上所述。

4 解法分析

这道题解法基本上有两种：深搜，数学方法

第一种：深搜解法

考虑到只需判断大小为三的环，那么我们可以尝试从每一个顶点出发，深搜三层，判断一下是否可以回到原来的顶点即可。

也可以先从一个点开始，记录当前的路径与步数。如果走到了之前走过的一个顶点且步数差恰好为3，那么输出即可。（这里提一嘴，竞赛图中，如果有环，则一定有大小为三的环）

第二种：数学解法

~~（数学解法不看博客打死我都想不出来）~~

考虑三个点x,y,z，且x -> y, x -> z, y -> z。
那么下证：x -> z这条边是没有用的。
首先，如果x -> z和b构成了环，（即z -> b, b -> x）
那么：

若y -> b,则x, y, b形成了环；
若b -> y,则b, y, z形成了环。
则x -> z的边没用。
那在忽略了若干条形如x -> z的边后，每一个点最多有一条出边。那我们只需要枚举两个点 $i, j$ ,来看看 $i,to_i,j$ 是否成环即可。

AC代码

ACCode #001

// From Heart_Blue
// Rating 2425
// reason : 思路清晰，代码简洁，运用了深搜来解题
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 5e3 + 10;
char a[N][N];
int vis[N];
int n;
void dfs(int x, int fa = -1)
{
    if (vis[x]) return;vis[x] = 1;for (int i = 0; i < n; i++){
    if (a[x][i] == '0') continue;if (fa != -1 && a[i][fa] == '1'){
    cout << fa + 1 << ' ' << x + 1 << ' ' << i + 1 << endl;exit(0);}dfs(i, x);}
}
int main()
{
    //freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%s", a[i]);for (int i = 0; i < n; i++) dfs(i);puts("-1");return 0;
}

ACCode #002

// From Endagorion
// Rating 3009
// reason : 思路清晰，代码简洁，用了path储存路径
#include <iostream>
#include <cmath>
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>using namespace std;bool dfs(int x, int n, vector< vector< bool > > &matrix,vector< int > &visited, vector< int > &path) {
    visited[x] = 1;path.push_back(x);for (int i = 0; i < n; ++i) {
    if (matrix[x][i]) {
    if (visited[i] == 1) {
    path.push_back(i);return true;}if (visited[i] == 0) {
    if (dfs(i, n, matrix, visited, path)) {
    return true;}}}}path.pop_back();visited[x] = 2;return false;
}int main() {
    int n;cin >> n;vector< string > edges(n);for (int i = 0; i < n; ++i) {
    cin >> edges[i];}vector< vector< bool > > matrix(n, vector< bool > (n));for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
    matrix[i][j] = edges[i][j] == '1';}}vector< int > path;vector< int > visited(n, 0);bool ok = false;for (int i = 0; i < n; ++i) {
    if (!visited[i]) {
    if (dfs(i, n, matrix, visited, path)) {
    ok = true;break;}}}if (!ok) {
    cout << -1 << '\n';} else {
    int i = path.size() - 3;int j = path.size() - 2;int k = path.size() - 1;while (true) {
    if (matrix[path[k]][path[i]]) {
    cout << path[i] + 1 << ' ' << path[j] + 1 << ' ' << path[k] + 1 << '\n';return 0;}--i; --j;}}return 0;
}

ACCode #003

// From stoorz
// Rating 2327
// reason : 思路清晰，代码简洁明了，运用了数学方法
#include <bits/stdc++.h>
using namespace std;const int N=5010;
int n,to[N];
char a[N][N];int main()
{
    scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%s",a[i]+1);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (a[i][j]==49 && (!to[i] || a[j][to[i]]==49)) to[i]=j;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (a[to[i]][j]==49 && a[j][i]==49)return printf("%d %d %d\n",i,to[i],j),0;printf("-1");return 0;
}