首页 > 代码库 > UVALive 6467 Strahler Order 拓扑排序

UVALive 6467 Strahler Order 拓扑排序

2024-07-15 18:50:00   212人阅读

这题是今天下午BNU SUMMER TRAINING的C题

是队友给的解题思路，用拓扑排序然后就可以了

最后是3A

其中两次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 long11 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 i67         }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\n",++numCase,ans[n]);89     }90     return 0;91 }

 


联系
我们