poj3660（floyd最短路）

题目链接：https://vjudge.net/problem/POJ-3660

题意：给出一个有向图，n个结点，每个结点的权值为[1,n]中的一个独特数字，m条边，如果存在边a->b，说明a的权值大于b，问能确定多少个点的权值。

思路：

　　用邻接矩阵存边，a[i][j]=1表示存在边i->j，然后跑floyd。

　　松弛操作为：如果a[i][j]==0&&a[i][k]==1&&a[k][j]==1，那么更新a[i][j]=1。

　　一个结点的权值能够确认的充要条件是它和其它n-1个点的关系确认。

AC code：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn=;

int ans,n,m,a[maxn][maxn];

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;++i){

        int u,v;

        scanf("%d%d",&u,&v);

        a[u][v]=;

    }

    for(int k=;k<=n;++k)

        for(int i=;i<=n;++i)

            for(int j=;j<=n;++j)

                if(!a[i][j]&&a[i][k]&&a[k][j])

                    a[i][j]=;

    for(int i=;i<=n;++i){

        int num=;

        for(int j=;j<=n;++j)

            if(a[i][j]||a[j][i]) ++num;

        if(num==n-) ++ans;

    }

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

    return ;

}

巴特西

poj3660（floyd最短路）

最新文章

热门文章