题解 P9980

· · 题解

题意：

一排点，可以从前往后连单向边（无重边），给定每两个点之间路径数，求总连边数。

思路：

我们要求的就是对于每两个点 i,j 满足 i<j，它们之间到底有没有单向边。设 t_{i,j}=0 表示没有单向边，t_{i,j}=1 表示有单向边。

考虑两点之间路径数是如何被计算出来的。设 G(i,j) 表示 i,j 之间的路径数（i<j），我们有：

G(i,j)=\sum_{k=i+1}^{j-1}t_{i,k}\times G(k,j)+t_{i,j}

即：考虑 i,j 之间的一个点 k，若 i,k 有连边，则答案增加 G(k,j)。最后再加上 i,j 间直连的个数。

因此我们就有了递推式子，可以参考其它题解，这里不重复给出。

程序如下：

#include<cstdio>
#include<cmath>
using namespace std;
const int N=755;
int n,ans;
char ch[N];
bool a[N][N],rt[N][N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%s",ch+1);
        for(int j=i+1;j<=n;j++)
            if(ch[j-i]=='1')
                a[i][j]=1;
    }
    for(int len=1;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            rt[i][j]=a[i][j];
            for(int k=i+1;k<j;k++)rt[i][j]^=(rt[i][k]&a[k][j]);
        }
    }
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            ans+=rt[i][j];
    printf("%d\n",ans);
    return 0;
}

THE END

USACO 2024 Dec RP++.