题解 P2835 【刻录光盘】

P2835 刻录光盘

来一波FLOYD最短代码qwq

#include<cstdio>

using namespace std;

#define FOR(i) for (register int i=1;i<=n;i++)

int n,x,a[201][201],f[201];

int main() {

    while(~scanf("%d",&n)) {

        FOR(i) while(scanf("%d",&x),x) a[i][x]=1;//建图，i可以将资料拷贝给x

        FOR(k) FOR(i) FOR(j) a[i][j]|=(a[i][k] && a[k][j]);//FLOYD：i和j本身可以到达或可经k到达，则i与j相连

        FOR(i) f[i]=i;

        FOR(i) FOR(j) if (a[i][j]) f[j]=f[i];//类似并查集，寻找祖先（入度为0的点）

        FOR(i) x+=(f[i]==i);//统计祖先数（即祖先不能从别的点拷贝到资料，所以每个祖先都需要一份）

        printf("%d\n",x);

    }

    return 0;

}

巴特西

题解 P2835 【刻录光盘】

P2835 刻录光盘

来一波FLOYD最短代码qwq

最新文章

热门文章