POJ 3275 Ranking the Cows(floyd 전달 클립)

Ranking the Cows
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 2248
 
Accepted: 1045
Description
Each of Farmer John's N cows (1 ≤ N ≤ 1,000) produces milk at a different positive rate, and FJ would like to order his cows according to these rates from the fastest milk producer to the slowest.
FJ has already compared the milk output rate for M (1 ≤ M ≤ 10,000) pairs of cows. He wants to make a list of C additional pairs of cows such that, if he now compares those C pairs, he will definitely be able to deduce the correct ordering of all N cows. Please help him determine the minimum value of C for which such a list is possible.
Input
Line 1: Two space-separated integers: 
N and 
M 
Lines 2..
M+1: Two space-separated integers, respectively: 
X and 
Y. Both 
X and 
Y are in the range 1...
N and describe a comparison where cow 
X was ranked higher than cow 
Y.
Output
Line 1: A single integer that is the minimum value of 
C.
Sample Input

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

Sample Output

3

Hint
From the information in the 5 test results, Farmer John knows that since cow 2 > cow 1 > cow 5 and cow 2 > cow 3 > cow 4, cow 2 has the highest rank. However, he needs to know whether cow 1 > cow 3 to determine the cow with the second highest rank. Also, he will need one more question to determine the ordering between cow 4 and cow 5. After that, he will need to know if cow 5 > cow 3 if cow 1 has higher rank than cow 3. He will have to ask three questions in order to be sure he has the rankings: "Is cow 1 > cow 3? Is cow 4 > cow 5? Is cow 5 > cow 3?"
Source
USACO 2007 March Gold
 
 
제목: FJ는 젖소가 젖을 낳는 능력에 따라 순위를 매기고 싶어 한다.현재는 N마리의 젖소(1≤N≤1000)가 있는 것으로 알려졌다.FJ는 비교를 통해 M(1≤M≤10000)의 상대적 관계를 이미 알고 있다.각 쌍의 관계는'XY'라고 표시하는데 X의 산유 능력이 Y보다 강하다는 것을 의미한다.현재 FJ는 적어도 몇 쌍의 관계를 조사해야만 전체 서열을 완성할 수 있는지 알고 싶어 한다.
사고방식: 정렬이 확정되면 잠재대사는 임의의 소 두 마리 사이의 관계를 모두 확정할 수 있다.N마리의 젖소는 모두 C(N,2)=N*(N-1)/2쌍의 관계가 있다.현재 알고 있는 관계가 K대 관계를 확인할 수 있다면 조사할 횟수는 C(N, 2)-K이다.
문제를 다시 한 번 생각해 보면 u가 v보다 강하면 u에서 v까지의 방향도 있다는 것을 알 수 있다.두 노드 사이에 관계가 있는 것은 이 두 노드 사이에 방향이 있는 것과 같다.이렇게 하면 임의의 두 점 사이에 경로 문제가 있는지 없는지,floyd로 패키지를 전달하면 된다.
그러나 최대 1000마리의 젖소가 있고 시간 복잡도는 O(N^3)이다.틀림없이 초과할 것이다. 생각해 보면 중간 노드 K를 하나하나 열거한 후에 u와 종점 v를 하나씩 들기 시작한다. 만약에 u와 K, 또는 v와 K 사이가 전혀 연결되지 않으면 절대로 느슨해질 수 없다.그래서 더 효율적인 방법은 시작점은 K로 통하는 노드만 검사하고 끝점은 K로 통하는 노드만 검사하는 것이다. 그러면 복잡도를 크게 낮출 수 있다. 왜냐하면 가장자리가 최대 10000개밖에 없기 때문이다.floyd는 사이드 테이블로 실현하고 공부했습니다.
 
 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 const int N=1010;
 8 
 9 int map[N][N],pre[N][N],suc[N][N];  //pre ，suc  pre[v][0] v ,suc[u][0] u 
10 
11 int main(){
12 
13     //freopen("input.txt","r",stdin);
14 
15     int n,m;
16     while(~scanf("%d%d",&n,&m)){
17         memset(map,0,sizeof(map));
18         memset(pre,0,sizeof(pre));
19         memset(suc,0,sizeof(suc));
20         int u,v;
21         int cnt=m;
22         while(m--){
23             scanf("%d%d",&u,&v);
24             map[u][v]=1;
25             pre[v][++pre[v][0]]=u;  //v u
26             suc[u][++suc[u][0]]=v;  //u v
27         }
28         int i,j,k;
29         for(k=1;k<=n;k++)
30             for(i=1;i<=pre[k][0];i++){
31                 u=pre[k][i];         //k u
32                 for(j=1;j<=suc[k][0];j++){
33                     v=suc[k][j];        //k v
34                     if(!map[u][v]){ //u k ，v k   u v 
35                         pre[v][++pre[v][0]]=u;   //u   v  
36                         suc[u][++suc[u][0]]=v;
37                         map[u][v]=1;
38                         cnt++;
39                     }
40                 }
41             }
42         printf("%d
",n*(n-1)/2-cnt);
43     }
44     return 0;
45 }