首页 > 代码库 > 【洛谷1983】车站分级
【洛谷1983】车站分级
显然，若停靠站点为a1,a2,a3......an,
则a1--an中，没有停靠的站点一定等级比停靠的站点低。
所以每一趟车次从每个低等级的点向每个高级连边。
之后拓扑，每次删去点i（满足1.入度为零，2.没有删掉，3.不是在本轮循环中通过减入度而使i入度为零的）
以及与i相邻的边。
1 #include <iostream> 2 #include<cstdio> 3 using namespace std; 4 int a[1001][1001]; 5 int t[1001][1001]; 6 bool is[1001][1001]; 7 int isnow[1001]; 8 int n,m; 9 bool ok[1001];10 int mini=10000,maxi=0;11 int main(){12 int p=0;13 scanf("%d %d",&n,&m);14 for (int i=1;i<=m;i++){15 cin>>a[i][0];16 for (int j=1;j<=a[i][0];j++){17 cin>>a[i][j];18 is[i][a[i][j]]=true;19 }20 for (int j=a[i][1];j<=a[i][a[i][0]];j++) {21 if (is[i][j]) continue;22 for (int k=1;k<=a[i][0];k++){23 if (t[a[i][k]][j]!=1) 24 t[a[i][k]][j]=1,t[0][j]++;25 }26 }27 mini=min(mini,a[i][1]);28 maxi=max(maxi,a[i][a[i][0]]);29 }30 while (1){31 p++;32 for (int i=mini;i<=maxi;i++){33 if (ok[i]==false && t[0][i]==0 && isnow[i]!=p) {34 for (int j=mini;j<=maxi;j++){35 if (t[i][j]==1){36 t[i][j]=0;37 t[0][j]--;38 isnow[j]=p;39 }40 }41 ok[i]=true;42 }43 }44 bool mark=true;45 for (int i=mini;i<=maxi;i++){46 if (ok[i]==false){47 mark=false;48 break;49 }50 }51 if (mark) break;52 }53 printf("%d",p);54 }
【洛谷1983】车站分级
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。