UVALLive 6467 Strahler Orderトポロジーソート
12882 ワード
この問題は今日の午後BNU SUMMER TRAININGのC問題です
チームメイトがくれた問題解きの考え方で、トポロジーで並べ替えておけばいいです.
最後は3 A
このうち2回のREは、
ORZ
あとでCINかCINかなQAQ
コードを貼りました:
チームメイトがくれた問題解きの考え方で、トポロジーで並べ替えておけばいいです.
最後は3 A
このうち2回のREは、
scanf("%d",mm);
ORZ
あとでCINかCINかなQAQ
コードを貼りました:
1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4 #include <math.h>
5 #include <iostream>
6 #include <stack>
7 #include <queue>
8 #include <algorithm>
9
10 #define ll long long
11 using namespace std;
12 const int INF = 0x3f3f3f3f;
13 const int MAXN = 8000;
14 int indgree[MAXN], map[MAXN][MAXN], ans[MAXN], cur[MAXN][MAXN];
15 int n;
16 void init(){
17 for(int i = 1; i <= n; ++i){
18 for(int j = 1; j <= n; ++j){
19 map[i][j] = i == j ? 0 : INF;
20 }
21 }
22 memset(indgree, 0, sizeof(indgree));
23 memset(ans, 0, sizeof(ans));
24 memset(cur, 0, sizeof(cur));
25 }
26
27 void insert_cur(int x, int num){
28 int pos = 1;
29 while(1){
30 if(cur[x][pos] == 0){
31 cur[x][pos] = num;
32 break;
33 }
34 ++pos;
35 }
36 }
37
38 int sigma_cur(int x){
39 int temp_ans = 0;
40 int Max = -INF;
41 for(int i = 1; cur[x][i] != 0; ++i){
42 if(cur[x][i] > Max) Max = cur[x][i];
43 }
44 int flag = 0;
45 for(int i = 1; cur[x][i] != 0; ++i){
46 if(cur[x][i] == Max) ++flag;
47 }
48 if(flag >= 2) ans[x] = ++Max;
49 else if(flag == 1) ans[x] = Max;
50 return ans[x];
51 }
52
53 void topsort(){
54 int i, j;
55 while(1){
56 for(i = 1; i <= n; ++i)
57 if(indgree[i] == 0) break;
58 if(i != n + 1){
59 for(j = 1; j <= n; ++j)
60 if(map[i][j] == 1){
61 map[i][j] = 0;
62 --indgree[j];
63 insert_cur(j, ans[i]);
64 if(indgree[j] == 0) ans[j] = sigma_cur(j);
65 }
66 indgree[i] = -1;//pop i
67 }
68 else break;
69 }
70 }
71
72 int main(){
73 int i, j, k, p, mm, a, b;
74 scanf("%d",&mm);
75 int numCase = 0;
76 while(mm--){
77 init();
78 scanf("%d%d%d",&k,&n,&p);
79 while(p--){
80 scanf("%d%d",&a,&b);
81 ++indgree[b];
82 map[a][b] = 1;
83 }
84 for(i = 1; i <= n; ++i){
85 if(indgree[i] == 0) ans[i] = 1;
86 }
87 topsort();
88 printf("%d %d
",++numCase,ans[n]);
89 }
90 return 0;
91 }