poj 3660 传递性关系 floyd更新

刺骨的言语ヽ痛彻心扉 2022-08-10 09:48 32阅读 0赞

Cow Contest

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 8664</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 4873</td> 
  </tr> 
 </tbody> 
</table>

Description

*N* (1 ≤ *N* ≤ 100) cows, conveniently numbered 1..*N*, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow *A* has a greater skill level than cow *B* (1 ≤ *A* ≤ *N*; 1 ≤ *B* ≤ *N*; *A* ≠ *B*), then cow *A* will always beat cow *B*.

Farmer John is trying to rank the cows by skill level. Given a list the results of *M* (1 ≤ *M* ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

Input

\* Line 1: Two space-separated integers: *N* and *M*  
\* Lines 2..*M*\+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, *A*, is the winner) of a single round of competition: *A* and *B*

Output

\* Line 1: A single integer representing the number of cows whose ranks can be determined

Sample Input

5 5
    4 3
    4 2
    3 2
    1 2
    2 5

Sample Output

题意：有一些优劣关系，具有传递性，比如a>b && b>c 那么a>c，此时如果有c>d，那么a也要大于d，b也大于d。

给定n头牛，有m个关系，让你判定有多少头牛的位置是确定了的。

分析：开始乱搞一通，然而并不能更新全部的关系，老是漏了。然后看题解是用floyd，感觉很巧妙。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=101;
    
    
    int win[N][N];
    void floyd(int n)
    {
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    win[i][j] |= win[i][k] && win[k][j];
                }
            }
        }
    }
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            mem(win,0);
            while(m--)
            {
                int x=in(),y=in();
                win[x][y]=1;
            }
            floyd(n);
            int ans=0;
            for(int i=1;i<=n;i++)
            {
                int t=0;
                for(int j=1;j<=n;j++)
                {
                    t += win[i][j] || win[j][i]; //i>j 或者 j>i
                }
                if(t == n-1) ans ++ ; //能够确定的关系有n-1个，就能确定i的位置
            }
            printf("%d\n",ans);
        }
        return 0;
    }