题解：P10944 Going from u to v or from v to u?

BK小鹿 · 2024-08-29 14:31:58 · 题解

题意简述

这题比较抽象，我就把我校 oj 的翻译放上来了。

给你一个有 n 个点 m 条边有向图，让你判断该图是否对于任意的一对顶点 (X,Y)，存在从 X 到 Y 的路径或者从 Y 到 X 的路径。

思路分析

首先，我们知道 floyd 可以稍微改改，把最短路改成是否连通，就可以写出这样一份暴力，具体看注释。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char *p1,*p2,buf[1<<20+5];
inline int read(){
    int x=0;
    char c=gc();
    while(!isdigit(c)){
        c=gc();
    }while(isdigit(c)){
        x=x*10+(c^48);
        c=gc();
    }return x;
}

const int N = 1005;

int T;
int n, m;
bool g[N][N];

int main()
{
    T = read();
    int x, y;
    while (T -- )
    {
        n = read(), m = read();
        memset(g, 0, sizeof(g)); 
        for (int i = 1; i <= n; i++) g[i][i] = 1; 
        for (int i = 0; i < m; i ++ )
        {
            x = read(), y = read();
            g[x][y] = 1;
        } 

        for (int k = 1; k <= n; k ++ )
            for (int i = 1; i <= n; i ++ )
                for (int j = 1; j <= n; j ++ )
                    g[i][j] = g[i][j] || (g[i][k] && g[k][j]);//从i到j可以直接到，或是从i到k，再从k到j

        bool flag = true;
        for (int i = 1; i <= n && flag; i ++ )
            for (int j = 1; j <= n && flag; j ++ )
                if (!g[i][j] && !g[j][i])
                    flag = false;

        if (!flag)  puts("No");
        else puts("Yes");
    }
    return 0;
}

但是，他显然会超时，只有60分。

怎么办呢，这个时候就可以使用 bitset 了，不知道的话可以看看这篇文章。

这样，我们复杂度就只有大概平方了，完全可以通过此题，记录。

放个代码。

#include <iostream>
#include <cstdio>
#include <bitset>
#include <cstring>

using namespace std;

#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char *p1,*p2,buf[1<<20+5];
inline int read(){
    int x=0;
    char c=gc();
    while(!isdigit(c)){
        c=gc();
    }while(isdigit(c)){
        x=x*10+(c^48);
        c=gc();
    }return x;
}

const int N = 1005;

int T;
int n, m;
bitset<N> g[N];

int main()
{
    T = read();
    int x, y;
    while (T -- )
    {
        n = read(), m = read();
        for (int i = 1; i <= n; i++) {
            g[i].reset();
            g[i][i] = 1; 
        }
        for (int i = 0; i < m; i ++ )
        {
            x = read(), y = read();
            g[x][y] = 1;
        } 

        for (int k = 1; k <= n; k ++ )
            for (int i = 1; i <= n; i ++ )
                if (g[i][k])
                    g[i] |= g[k];

        bool flag = true;
        for (int i = 1; i <= n && flag; i ++ )
            for (int j = 1; j <= n && flag; j ++ )
            {
                if (!g[i][j] && !g[j][i]) {
                    flag = false;
                }  
            }

        if (!flag)  puts("No");
        else puts("Yes");
    }
    return 0;
}