POJ 3660 Cow Contest ( 最短路松弛思想应用 && Floyd求传递闭包 )

题意 : 给出 N 头奶牛在比赛的结果,问你最多的能根据给出结果确定其名次的奶牛头数。结果给出的形式为 A  B 代表在比赛当中 A 战胜了 B

分析 : 对于一头奶牛来说,如果我们能确定其他 N - 1 头奶牛和它的关系,那么它的名次就确定了。将奶牛之间的胜负关系建图,如果给出 A B 那么我们建一条 A->B 的边,代表 A 能战胜 B ,当然也表示了 A 和 B 能确立关系,那么现在有一头奶牛 C 且有 C->A 即其与 A 的关系是确定的,那么 B 和 C 的关系是否能确定呢?毋庸置疑,当然可以,关系为 C->A->B ,但是通过 A 这个中间人来确定 C 和 B 的关系实在麻烦,既然两点有边即为关系确立,那么能不能将 C->A->B 这条边松弛为 C->B ?是不是像极了最短路里面的松弛操作。数据不大,实际上这也是一个求传递闭包的过程,可以用 Floyd 做,用二维数组 G 存图,且初始化为 0 ,如果 G[i][j] 或者 G[j][i] 不为 0 那么代表 i 和 j 有关系,可见 Floyd 中状态转移方程改为 G[i][j] |= (G[i][k]&&G[k][j]) 即可,最后对于每一头牛判断一下,是否有 N-1 头牛和其有关系即可!

#include<bits/stdc++.h>
using namespace std;
;

int G[maxn][maxn];

int main(void)
{
    int N, M;
    scanf("%d %d", &N, &M);
    int from, to;
    ; i<=M; i++)
        scanf("%d %d", &from, &to),
        G[;

    ; k<=N; k++)
        ; i<=N; i++)
            ; j<=N; j++)
                G[i][j] |= (G[i][k]&&G[k][j]);

    ;
    ; i<=N; i++){
        ;
        ; j<=N; j++){
            if(i!=j) { if(G[i][j] || G[j][i]) Num--; }
        }if(!Num) ans++;
    }

    printf("%d\n", ans);
    ;
}
上一篇:ASP.NET MVC 4 Optimization的JS/CSS文件动态合并及压缩


下一篇:2014年百度之星程序设计大赛 - 资格赛 1001 Energy Conversion