P2881 [USACO07MAR]Ranking the Cows G（传递闭包模板题）

· · 题解

传递闭包的四种求法

有向图传递闭包需要对每个点对 (i,j)，求出 i 到 j 是否连通。

做法 1：

直接 Floyd，b_{i,j}=1 表示 i 能到达 j，b_{i,j}=0 表示不能到达。

枚举中转点 i，再枚举 j,k，转移方程：b[j][k]|=b[j][i]&b[i][k]。

可以用 bitset 优化：if(b[j][i])b[j]|=b[i]。

时间复杂度 O(\dfrac{n^3}{w})。

做法 2：

以每个点为起点深/广搜遍历整张图，求出能到达的所有点。

时间复杂度 O(nm)。

做法 3：

上一个做法不能用 bitset 优化，是因为可能存在环，不能记忆化。

考虑对强连通分量缩点（此题中保证是 DAG 就不用了）。

然后继续用做法 2，以每个点为起点 dfs。

若当前访问到边 (i,j)，j 未被 dfs 过，则 dfs j。

然后 b[i]|=b[j]。

时间复杂度 O(\dfrac{nm}{w})。

适合稀疏图，在此题中效率最高。

做法 4：

依然是先缩点。

然后求出 DAG 的拓扑序。

按拓扑序每 B 个点分一块，倒序求解。

对于每一块，在求出其中所有点的可达集合后，求出 2^B 个子集的可达集合（一个子集的可达集合是其中所有点可达集合的并集），用 bitset 优化，这部分复杂度 O(2^B\dfrac{n}{B}\dfrac{n}{w})。

求一个点 i 的可达集合，只需要枚举之后的每个块，通过子集的可达集合，一次更新以块中所有存在边 (i,j) 的点 j 为中转点的答案，这部分复杂度 O(n\dfrac{n}{B}\dfrac{n}{w})。

取 B=\log n，总复杂度 O(\dfrac{n^3}{w\log n})。

适合稠密图。

代码中取 B=8。

最后提一下此题做法。

显然是传递闭包模板题。

最坏情况下，所有不能确定大小关系的都要问一遍。

所以答案即为总的满足 i\neq j 的无序对数 \dfrac{n\times(n-1)}{2}，减去已经确定大小关系的对数。

已经确定大小关系的对数，就是满足 i 能到达 j 且 i\neq j 的数对 (i,j) 个数。

做法 1

#include<bits/stdc++.h>
using namespace std;
const int N=1009;
bitset<N>b[N];
int main(){
    int n,m,i,j;
    for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&i,&j),b[i][j]=1;
    for(i=1;i<=n;++i)for(j=1;j<=n;++j)if(b[j][i])b[j]|=b[i];
    for(j=n*(n-1)/2,i=1;i<=n;++i)j-=b[i].count();
    printf("%d",j);
    return 0;
}

做法 2

#include<bits/stdc++.h>
using namespace std;
const int N=1009;
bool b[N];
int s;
basic_string<int>g[N];
void dfs(int x){for(int i:g[x])if(!b[i])b[i]=1,--s,dfs(i);}
int main(){
    int n,m,i,j;
    for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&i,&j),g[i]+=j;
    for(i=1,s=n*(n-1)/2;i<=n;++i)memset(b,0,N),dfs(i);
    printf("%d",s);
    return 0;
}

做法 3

#include<bits/stdc++.h>
using namespace std;
const int N=1009;
bitset<N>b[N];
basic_string<int>g[N];
void dfs(int x){
    b[x][x]=1;
    for(int i:g[x]){
        if(!b[i][i])dfs(i);
        b[x]|=b[i];
    }
}
int main(){
    int n,m,i,j;
    for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&i,&j),g[i]+=j;
    for(i=1,j=n*(n+1)/2;i<=n;++i)dfs(i),j-=b[i].count();
    printf("%d",j);
    return 0;
}

做法 4

#include<bits/stdc++.h>
using namespace std;
const int N=1009;
basic_string<int>g[N];
int p[N],d[N],q[N];//p[i]表示i在拓扑序的逆序中的排名
bool e[N][N];
bitset<N>b[N],o[259];
int main(){
    int n,m,i,j,l=0,r=0;
    for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&i,&j),g[i]+=j,++d[j];
    for(i=1;i<=n;++i)if(!d[i])q[++r]=i;//拓扑排序入队
    while(l<r){//拓扑排序
        i=q[++l],p[i]=n-l+1;
        for(int o:g[i])if(!(--d[o]))q[++r]=o;
    }
    for(i=1;i<=n;++i)for(int o:g[i])e[p[i]][p[o]]=1;//重新建边，i>j时e[i][j]才可能等于1
    for(i=1;i<=n;++i)if(b[i][i]=1,!(i&7)){
        for(j=1;j<256;++j)l=j&-j,o[j]=o[j^l]|b[i-7+__lg(l)];//求出一块的子集的bitset
        for(j=i+1;j<=n;b[j++]|=o[l])for(r=l=0;r<8;++r)if(e[j][i-7+r])l|=1<<r;//用子集的bitset更新之后的所有点
    }else for(j=min(n,i/8*8+8);j>i;--j)if(e[j][i])b[j]|=b[i];//更新当前块之后的点
    for(i=1,j=n*(n+1)/2;i<=n;++i)j-=b[i].count();
    printf("%d",j);
    return 0;
}