B3611 【模板】传递闭包题解

银杉水杉秃杉 · 2021-10-27 15:36:29 · 题解

喜提此题最优解！

本题小故事：这道题本来在主题库，由于过于简单，经过 LA 群激烈的讨论，被某位管理员迁移到了入门与面试。

传递闭包，没有什么可以过多介绍的，就是传统 Floyd 的想法。

复杂度：O(n^3)

#include <bits/stdc++.h>
using namespace std;
int n;
int a[110][110];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    for (int k = 1; k <= n; k++)//记得k循环在i和j之前
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                a[i][j] |= a[i][k] & a[k][j];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

虽然 Floyd 能通过这道题，但 Floyd 是 O(n^3) 的算法，太慢了。

思考：如果把这道题的数据范围换成 n\le2000 该怎么办呢？

以下提供两种优化思路。

第一种为 bitset 优化，相对来说跑的要快一些。

这种方法也很好写，目前是此题的最优解（21ms）。

最优解AC记录

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        f = ch != '-';
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return f ? x : -x;
}
int n;
bitset<110> a[110];
int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = read();
    for (int j = 1; j <= n; j++)//注意j循环在i循环外
        for (int i = 1; i <= n; i++)
            if (a[i][j])
                a[i] |= a[j];//bitset也挺好写的
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            putchar(a[i][j] + '0'), putchar(' ');
        putchar('\n');
    }
    return 0;
}

第二种为压位优化，就是把连续 32 个点的状态压缩成一个 int 类型的数，类似于状压dp。这样既节省了空间，也节约了时间。

代码只要理解了，还是挺好写的。虽然 bitset 肯定最好写的，但如果不想用 STL 的话，压位肯定是最好的，只是要注意的细节很多。

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int n,m,a[N][N];
char c;
int main ()
{
    scanf("%d",&n);
    m=n/32+1;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            for (int k=0;k<32&&j*32+k<n;k++)
            {
                char c=getchar();
                while (c!='0'&&c!='1') 
                    c=getchar();
                a[i][j]|=(c-'0')<<k;
            }
    for (int k=0;k<n;k++)
        for (int i=0;i<n;i++)
        {
            int f=-((a[i][k/32]>>(k%32))&1);
            if (f==0) 
                continue;
            for (int j=0;j<m;j++)
                a[i][j]=a[i][j]|(f&a[k][j]);
        }
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<m;j++)
            for (int k=0;k<32&&j*32+k<n;k++)
                putchar(((a[i][j]>>k)&1)+'0'),putchar(' '); 
        putchar('\n');
    }
    return 0;
}

综上所述，我还是更推荐大家写 bitset。STL 的快乐，只有用过才会知道。

B3611 【模板】传递闭包 题解

B3611 【模板】传递闭包题解