【NOIP2013 普及组】车站分级

一、题目

【NOIP2013 普及组】车站分级

时间限制: 1 Sec 内存限制: 128 MB
提交: 3 解决: 0
[提交][状态][讨论版]

题目描述

一条单向的铁路线上，依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）

例如，下表是 5 趟车次的运行情况。其中，前 4 趟车次均满足要求，而第 5 趟车次由于停靠了 3 号火车站（2 级）却未停靠途经的 6 号火车站（亦为 2 级）而不满足要求。

现有 m 趟车次的运行情况（全部满足要求），试推算这 n 个火车站至少分为几个不同的级别。

输入

输入文件为 level.in。

第一行包含 2 个正整数 n, m，用一个空格隔开。

第 i + 1 行（1 ≤ i ≤ m）中，首先是一个正整数 si（2 ≤ si ≤ n），表示第 i 趟车次有 si 个停靠站；接下来有 si个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

输出

输出文件为 level.out。

输出只有一行，包含一个正整数，即 n 个火车站最少划分的级别数。

样例输入

输入样例#1：

9 2

4 1 3 5 6

3 3 5 6

输入样例#2：

9 3

4 1 3 5 6

3 3 5 6

3 1 5 9

样例输出

输出样例#1：

输出样例#2：

提示

对于 20%的数据，1 ≤ n, m ≤ 10；
对于 50%的数据，1 ≤ n, m ≤ 100；
对于 100%的数据，1 ≤ n, m ≤ 1000。

二、分析及代码

首先考虑50%的数据，我们知道对于每一列车，它经过的站点中停了的站点的等级肯定比没停的站点高。因此对于每一辆车，我们可以把它经过的每一个没停的站点向每一个停了的站点建一条边。然后我们会得到一张图，在这张图上找最长的一条路段即可。

然后考虑正解，显然对于点考虑是无法再优化了，因此我们考虑车。我们定义一辆车的等级就是它经过站点的最小等级。我们考虑如何判定两辆车的等级大小。

对于两辆车，它们如果没有交点，那么它们的等级没有关系。

两辆车相交区间（都有停的区间）中，如果一辆车停的车辆多，那么它的等级低。

于是我们就建立了两辆车之间的大小关系，同样的，应用拓扑排序就可以找到这个最大的等级。

最后，还有一点要注意，因为我们处理的是车，而最后要求的是点。如果对于一辆等级为1的车，它经过的站点中如果有一个站点一辆车都没有停靠，那么最后的答案就要加1。

对于测试数据二：

9 3
4 1 3 5 6
3 3 5 6
3 1 5 9

比如第二辆车和第三辆车，都停了站5，但是第三辆车没有停3，所以第三辆车优先级比第二辆车高。

比如第一辆车和第二辆车的确有共同停靠站，且第一辆车停的站的确比第二辆车多，但是并不能说明第一辆车的等级低于第二辆车，因为起始站不同。

增加一辆每个站都停的列车，来作为等级最低的列车。

因为经过前面我们可以求出所有列车的等级，但是里面等级最低的一辆车要是有一个站没停，就存在着更低的一辆列车。这样才是正确的把点的等级转化为站的等级。

逻辑为：

在两辆车的最大共同区域里面，（1）有共同的站，（2）但是如果一辆车经过的站多，那么等级低。

问题分解为：

1、找两辆车的最大公共区域（好找，头里面的较大值，尾巴上的较小值）

2、计算公共区域里面的停靠站数

3、车辆数多的等级低

代码：

50分

  1 /*
  2 分析： 
  3 低优先度节点指向高优先度节点 
  4 */ 
  5 
  6 #include <iostream>
  7 #include <queue>
  8 #define Maxn 1005
  9 using namespace std;
 10 int n,m;
 11 // stopStation[i][j]表示第i辆车停靠的第j站， stopStation[i][0]表示第i辆车停靠的车站数 
 12 int stopStation[Maxn][Maxn];
 13 // adjacentMatrix[i][j]为true表示j车站的优先级比i车站高 
 14 // 停了的站的优先级比没停的高 
 15 bool adjacentMatrix[Maxn][Maxn];
 16 bool station[Maxn]; 
 17 int inDegree[Maxn];
 18 //队列里面储存入度为0（也就是当前优先级最低）的节点的编号， 
 19 queue<int> que; 
 20 bool vis[Maxn];
 21 
 22 int priority[Maxn];
 23 int maxPriority;
 24 
 25 void readData(){
 26     cin>>n>>m; 
 27     for(int i=1;i<=m;i++){
 28         cin>>stopStation[i][0];
 29         for(int j=1;j<=stopStation[i][0];j++){
 30             cin>>stopStation[i][j];
 31         }
 32     }
 33 }
 34 
 35 void printRead(){
 36     cout<<"n:"<<n<<" m:"<<m<<endl;
 37     for(int i=1;i<=m;i++){
 38         for(int j=0;j<=stopStation[i][0];j++){
 39             cout<<stopStation[i][j]<<" ";
 40         }
 41         cout<<endl;
 42     }
 43 }
 44 
 45 void initArr_station(int i){
 46     for(int j=1;j<=n;j++){
 47         station[j]=false;
 48     }
 49     for(int j=1;j<=stopStation[i][0];j++){
 50         int x=stopStation[i][j];
 51         station[x]=true;
 52     }
 53 }
 54 
 55 void printArr_station(){
 56     for(int j=1;j<=n;j++){
 57         cout<<station[j]<<" ";
 58     }
 59     cout<<endl;
 60 }
 61 
 62 void initArr_adjacentMatrix(){
 63     for(int i=1;i<=n;i++){
 64         for(int j=1;j<=n;j++){
 65             adjacentMatrix[Maxn][Maxn]=false;
 66         }
 67     }
 68     //起点站之前的站是没有经过，但是优先级并不比那些停了的站低 
 69     //所以我比较优先级只能从起点站开始 
 70     //我也只能以终点站结束
 71     for(int i=1;i<=m;i++){
 72         initArr_station(i);
 73         int endStation=stopStation[i][stopStation[i][0]]; 
 74         for(int j=stopStation[i][1];j<=endStation;j++){
 75             if(station[j]) continue;
 76             for(int k=stopStation[i][1];k<=endStation;k++){
 77                 if(station[k]){
 78                     adjacentMatrix[j][k]=true;
 79                 }
 80             }
 81         }
 82     } 
 83 }
 84 
 85 void printArr_adjacentMatrix(){
 86     for(int i=1;i<=n;i++){
 87         for(int j=1;j<=n;j++){
 88             cout<<adjacentMatrix[i][j]<<" ";
 89         }
 90         cout<<endl;
 91     }
 92 }
 93 
 94 void initArr_inDegree(){
 95     for(int i=1;i<=n;i++){
 96         inDegree[i]=0;
 97     }
 98     for(int i=1;i<=n;i++){
 99         for(int j=1;j<=n;j++){
100             if(adjacentMatrix[i][j]){
101                 inDegree[j]++;
102             }
103         }
104     }
105 }
106 
107 void printArr_inDegree(){
108     for(int i=1;i<=n;i++){
109         cout<<inDegree[i]<<" ";
110     }
111     cout<<endl;
112 }
113 
114 void initArr_vis(){
115     for(int i=1;i<=n;i++){
116         vis[i]=false;
117     }
118 }
119 
120 void printArr_vis(){
121     for(int i=1;i<=n;i++){
122         cout<<vis[i]<<" ";
123     }
124     cout<<endl;
125 }
126 
127 void initArr_priority(){
128     for(int i=1;i<=n;i++){
129         priority[i]=0;
130     }
131 }
132 
133 void printArr_priority(){
134     for(int i=1;i<=n;i++){
135         cout<<priority[i]<<" ";
136     }
137     cout<<endl;
138 }
139 
140 
141 void init(){
142     readData();
143     //printRead();
144     //initArr_station(2);
145     //printArr_station();
146     initArr_adjacentMatrix();
147     //printArr_adjacentMatrix();
148     initArr_inDegree();
149     //printArr_inDegree();
150     initArr_vis();
151     initArr_priority();
152     //printArr_priority();
153 }
154 
155 void removeConnection(int i1){
156     for(int j=1;j<=n;j++){
157         adjacentMatrix[i1][j]=false;
158     }
159 }
160 
161 void topologicalSorting(){
162     for(int i=1;i<=n;i++){
163         if(inDegree[i]==0&&!vis[i]){
164             vis[i]=true;
165             que.push(i);
166             priority[i]=1;
167         }
168     } 
169     while(!que.empty()){
170         int i1=que.front();
171         que.pop();
172         removeConnection(i1);
173         initArr_inDegree();
174         //printArr_inDegree();
175         for(int i=1;i<=n;i++){
176             if(inDegree[i]==0&&!vis[i]){
177                 vis[i]=true;
178                 que.push(i);
179                 priority[i]=priority[i1]+1;
180             }
181         }
182     }
183 }
184 
185 void findHighestPriority(){
186     maxPriority=0;
187     for(int i=1;i<=n;i++){
188         if(priority[i]>maxPriority){
189             maxPriority=priority[i];
190         }    
191     }
192 }
193 
194 void printAns(){
195     //printArr_priority();
196     findHighestPriority();
197     cout<<maxPriority<<endl;
198 }
199 
200 int main(){
201     freopen("4in.txt","r",stdin);
202     init();    
203     topologicalSorting();
204     printAns();
205     return 0;
206 } 
207 
208 /*
209 1、1，n不一定是起点和终点
210 起点站之前的站是没有经过，但是优先级并不比那些停了的站低 
211 所以我比较优先级只能从起点站开始 
212 2、起点终点不一定是从0开始 
213 */

80分，比较车的等级

  1 #include <iostream>
  2 #include <queue>
  3 using namespace std;
  4 //记录每辆车停的每个站 stopStation[i][0]表示第i辆车停靠的站 
  5 int stopStation[1005][1005];
  6 int n,m;
  7 bool adjacentMatrix[1005][1005];
  8 //每一辆车的入度 
  9 int inDegree[1005];
 10 bool vis[1005];
 11 //每一辆车的等级 
 12 int priority[1005];
 13 //最大的等级，因为是从1开始，所以这个值就是答案 
 14 int maxPriority;
 15 //队列里面储存入度为0（也就是当前优先级最低）的节点的编号， 
 16 //用来做拓扑排序的队列 
 17 queue<int> que; 
 18 
 19 //读取数据 
 20 void readData(){
 21     cin>>n>>m;
 22     for(int i=1;i<=m;i++){
 23         cin>>stopStation[i][0];
 24         for(int j=1;j<=stopStation[i][0];j++){
 25             cin>>stopStation[i][j];
 26         }
 27     } 
 28 }
 29 
 30 //打印读取的数据 
 31 void printRead(){
 32     cout<<"n:"<<n<<" m:"<<m<<endl;
 33     for(int i=1;i<=m;i++){
 34         for(int j=0;j<=stopStation[i][0];j++){
 35             cout<<stopStation[i][j]<<" ";
 36         }
 37         cout<<endl;
 38     }
 39 }
 40 
 41 //增加一辆每个站都停的0号列车 
 42 void  initArr_stopStation(){
 43     stopStation[0][0]=n;
 44     for(int j=1;j<=stopStation[0][0];j++){
 45         stopStation[0][j]=j;
 46     }
 47 }
 48 
 49 //打印数据 stopStation
 50 void printArr_stopStation(){
 51     cout<<"n:"<<n<<" m:"<<m<<endl;
 52     for(int i=0;i<=m;i++){
 53         for(int j=0;j<=stopStation[i][0];j++){
 54             cout<<stopStation[i][j]<<" ";
 55         }
 56         cout<<endl;
 57     }
 58 }
 59 
 60 //找两辆车(第i辆和第j辆)的最大公共区域（好找，头里面的较大值，尾巴上的较小值）
 61 void commonPathArea(int i,int j,int &start,int &end){
 62     int startI=stopStation[i][1];
 63     int endI=stopStation[i][stopStation[i][0]];
 64     int startJ=stopStation[j][1];
 65     int endJ=stopStation[j][stopStation[j][0]];
 66     start=max(startI,startJ);
 67     end=min(endI,endJ); 
 68 }
 69 
 70 // 计算第i辆车公共区域[start、end]里面的停靠站数 
 71 int stopStationNum(int i,int start,int end){
 72     int num=0;
 73     for(int j=1;j<=stopStation[i][0];j++){
 74         if(stopStation[i][j]>end) break;
 75         if(stopStation[i][j]>=start&&stopStation[i][j]<=end) num++;
 76     }
 77     return num;
 78 } 
 79 
 80 //比较i，j两辆车的等级
 81 int compareGrade(int i,int j){
 82     int start,end;
 83     commonPathArea(i,j,start,end);
 84     int numI=stopStationNum(i,start,end);
 85     int numJ=stopStationNum(j,start,end);
 86     if(numI==numJ) return 0;
 87     else if(numI<numJ) return 1;//i的等级高 
 88     else if(numI>numJ) return -1;
 89 } 
 90 
 91 //初始化数据 adjacentMatrix
 92 void initArr_adjacentMatrix(){
 93     for(int i=0;i<=m;i++){
 94         for(int j=0;j<=m;j++){
 95             adjacentMatrix[i][j]=false;
 96         }
 97     }
 98 }
 99 
100 //创建图 
101 void creatGraph(){
102     for(int i=0;i<=m-1;i++){
103         for(int j=i+1;j<=m;j++){
104             if(compareGrade(i,j)==1) adjacentMatrix[j][i]=true;
105             else if(compareGrade(i,j)==-1) adjacentMatrix[i][j]=true;
106         }
107     }
108 }
109 
110 //打印图 
111 void printGraph(){
112     for(int i=0;i<=m;i++){
113         for(int j=0;j<=m;j++){
114             cout<<adjacentMatrix[i][j]<<" ";
115         }
116         cout<<endl;
117     }
118 }
119 
120 //初始化每辆车的入度 
121 void initArr_inDegree(){
122     for(int i=0;i<=m;i++)
123         inDegree[i]=0;
124 }
125 
126 //打印每辆车的入度 
127 void printArr_inDegree(){
128     for(int i=0;i<=m;i++)
129         cout<<inDegree[i]<<" ";
130     cout<<endl;
131 }
132 
133 //得到每辆车的入度 
134 void getInDegree(){
135     for(int i=0;i<=m;i++){
136         for(int j=0;j<=m;j++){
137             if(adjacentMatrix[i][j]) inDegree[j]++;
138         }
139     }
140 }
141 
142 //初始化数据vis 
143 void initArr_vis(){
144     for(int i=0;i<=m;i++)
145         vis[i]=false;
146 }
147 
148 //初始化数据 priority
149 void initArr_priority(){
150     for(int i=0;i<=m;i++)
151         priority[i]=0;
152 }
153 
154 //打印数组 priority
155 void printArr_priority(){
156     for(int i=0;i<=m;i++)
157         cout<<priority[i]<<" ";
158     cout<<endl;
159 }
160 
161 //取消节点i到其它节点的连接 
162 void removeConnection(int i){
163     for(int j=0;j<=m;j++){
164         if(adjacentMatrix[i][j]) inDegree[j]--;
165     }
166 }
167 
168 //拓扑排序 
169 void topologicalSorting(){
170     for(int i=0;i<=m;i++){
171         if(inDegree[i]==0&&!vis[i]){
172             vis[i]=true;
173             que.push(i);
174             priority[i]=1;
175         }
176     } 
177     //printArr_priority();
178     while(!que.empty()){
179         int i1=que.front();
180         que.pop();
181         removeConnection(i1);
182         for(int i=0;i<=m;i++){
183             if(inDegree[i]==0&&!vis[i]){
184                 vis[i]=true;
185                 que.push(i);
186                 priority[i]=priority[i1]+1;
187             }
188         }
189     }
190 }
191 
192 //找到最高优先级 
193 void findHighestPriority(){
194     maxPriority=0;
195     for(int i=0;i<=m;i++){
196         if(priority[i]>maxPriority){
197             maxPriority=priority[i];
198         }    
199     }
200 }
201 
202 
203 //打印结果 
204 void printAns(){
205     //printArr_priority();
206     findHighestPriority();
207     cout<<maxPriority<<endl;
208 }
209 
210 //初始化 
211 void init(){
212     //读取数据 
213     readData();
214     //printRead();
215     //初始化数据 stopStation()
216     initArr_stopStation();//增加一辆每个站都停的0号列车 
217     //printArr_stopStation();
218     //initArr_adjacentMatrix();
219     //创建图 
220     creatGraph();
221     //printGraph(); 
222     //initArr_inDegree();
223     //得到每辆车的入度 
224     getInDegree();
225     //printArr_inDegree();
226     //initArr_vis();
227     //initArr_priority();
228     
229 }
230 
231 
232 int main(){
233     freopen("4in.txt","r",stdin);
234     //初始化 
235     init();
236     //拓扑排序 
237     topologicalSorting();
238     //打印结果 
239     printAns();
240     return 0;
241     
242 }

90分还是比较站的等级，输入时优化

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 const int N=1e3+5,INF=1e9+5;
 7 inline int read(){
 8     char c=getchar();int x=0,f=1;
 9     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
10     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
11     return x*f;
12 }
13 int n,m,s,g[N][N],vis[N],lst[N],ind[N],ans=0;
14 int st[N],top=0,buf[N],top2=0;
15 void toposort(){
16     for(int i=1;i<=n;i++) if(ind[i]==0) st[++top]=i;
17     while(top){
18         ans++;//printf("hi %d %d
",ans,del);
19         while(top){
20             int u=st[top--];  //printf("u %d
",u);
21             for(int v=1;v<=n;v++) if(g[u][v]){
22                 ind[v]--;   //printf("v %d %d
",v,ind[v]);
23                 if(ind[v]==0) buf[++top2]=v;
24             }
25         }
26         for(int i=1;i<=top2;i++) st[i]=buf[i];
27         top=top2;
28         top2=0;
29     }
30 }
31 
32 //这是在读数据的时候就完成了各种初始化，减少了循环次数，所以可以多得分 
33 int main(){
34     freopen("4in.txt","r",stdin);
35     n=read();m=read();
36     for(int i=1;i<=m;i++){
37         s=read();
38         memset(vis,0,sizeof(vis));
39         for(int j=1;j<=s;j++) lst[j]=read(),vis[lst[j]]=1;
40         for(int j=lst[1];j<=lst[s];j++) if(!vis[j])
41             for(int k=1;k<=s;k++) if(!g[lst[k]][j]) g[lst[k]][j]=1,ind[j]++;
42     }
43     toposort();
44     printf("%d",ans);
45 }