自动搬运

查看原文

来自洛谷，原作者为

	银杉水杉秃杉 原神OI堂主 QQ群853353679 详细主页在博客

搬运于2025-08-24 21:13:54，当前版本为作者最后更新于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 的快乐，只有用过才会知道。