洛谷P2419 [USACO08JAN]牛大赛Cow Contest

对于一个能够确定名次的点，可以注意到，对于该点，入度和出度的数量加起来等于N-1
（这样还是不够准确的
确切的说是，能够到达这个点的数量和这个点能够到达的数量的和

floyd不仅可以求两个点之间的最短路径，还能求两个点彼此是否能够相互到达
最后对于一个可以确定名次的点，能够到达的所有的点加上能够到达该点的所有点的和必须等于n-1
当然，我们可以通过二进制来简化这个过程

最后处理结果时，设一个变量flag, 因为该点能够到达本身，flag初值赋为1
对于两个点i, j首先f[i][j] | f[j][i]
因为对于这两个点，无论从j到i或是从i到j，都需算上。
同时用flag与f[i][j] | f[j][i]相&
按位与的操作是两位全为1，则得到的值为1，也就是说，若有任何一点不能到达此点或是由此点到达，我们就无法求出该点的名次
最后我们用计数器ans累加flag的值即可

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 int n, m, ans = ;

 int f[maxn][maxn];

 inline int read() {

     int x = , y = ;

     char ch= getchar();

     while(!isdigit(ch)) {

         if(ch == '-') y = -;

         ch = getchar();

     }

     while(isdigit(ch)) {

         x = (x << ) + (x << ) + ch - '';

         ch = getchar();

     }

     return x * y;

 }

 int main() {

     n = read(), m = read();

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

         int x, y;

         x = read(), y = read();

         f[x][y] = ;

     }

     for(int k = ; k <= n; ++k)//floyd求两个点能否互相到达

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

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

                 f[i][j] |= f[i][k] & f[k][j];

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

         int flag = ;//判断i点是否能够求出具体的名次

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

             if(i == j) continue;

             else flag &= f[i][j] | f[j][i];

         }

         ans += flag;//统计答案

     }

     cout << ans << '\n';

     return ;

 }

巴特西

洛谷P2419 [USACO08JAN]牛大赛Cow Contest

最新文章

热门文章