拓扑排序&车站分级
拓扑排序
使用范围
在不存在互相指向的节点的有向图中。
如何操作
入度与出度
一个点的入度记录的是指向这个点的其他节点的数量
一个点的出度记录的是这个点指向的点的数量
排序方法
1.找到这个图中所有入度为0的节点。
2.将这写节点指向的节点的入度--。
3.删除这个节点(并记录下来)。
动图:https://www.cs.usfca.edu/~galles/visualization/TopoSortIndegree.html
//本段代码摘自百度
queue<int>q;
//priority_queue<int,vector<int>,greater<int>>q;
//优先队列的话,会按照数值大小有顺序的输出
//此处为了理解,暂时就用简单队列
inttopo()
{
for(inti=1;i<=n;i++)
{
if(indegree[i]==0)
{
q.push(i);
}
}
int temp;
while(!q.empty())
{
temp=q.front();//如果是优先队列,这里可以是top()
printf("%d->",temp);
q.pop();
for(inti=1;i<=n;i++)//遍历从temp出发的每一条边,入度--
{
if(map[temp][i])
{
indegree[i]--;
if(indegree[i]==0)q.push(i);
}
}
}
}
不会vector存图可以先用邻接矩阵。
车站分级
由于停靠了x车站,级别大于x车站的车站也要停。于是推得没有停靠的车站一定小于停靠的车站。(只限于起点站到终点站的区间内,这里我卡了好久)
我们就用这一个大小关系建一个图:已知的级别较小的车站指向级别较大的车站。
入度为0的点就代表现在的已知条件下,没有点保证比它更小,所以可以用类拓扑排序的方式将这些入度为0的点全部删掉。
然后一层一层删下去
直到发现没有入度为0的点,即没有剩余的点。就输出层数。
#include<bits/stdc++.h>
using namespace std;
int tu[1005][1005];
int rudu[1005];
int ans;
bool used[1005];
int main(){
// freopen("testdata.in","r",stdin);
int n,m;
cin>>n>>m;
int tai[1005],x;
//建图,算出入度
for(int i=0;i<m;i++){
bool kao[1005];//1代表靠站,0代表不靠站
memset(kao,0,sizeof(kao));
cin>>x;
for(int j=0;j<x;j++){
cin>>tai[j];
kao[tai[j]]=1;
}
for(int j=tai[0];j<=tai[x-1];j++){//一定要在起点和终点之间啊啊啊!
if(!kao[j]){
for(int k=0;k<x;k++){
if(!tu[j][tai[k]]){
tu[j][tai[k]]=1;
rudu[tai[k]]++;
}
}
}
}
}
int cnt=10;
int mem[1005];
//拓扑
while(cnt!=0){
cnt=0;
for(int i=1;i<=n;i++){
if(rudu[i]==0&&used[i]==0){//为了不再删删过的点,用used表示已删除的点
mem[++cnt]=i;
used[i]=1;
}
}
for(int i=1;i<=cnt;i++){
for(int j=1;j<=n;j++){
if(tu[mem[i]][j]){
tu[mem[i]][j]=0;
rudu[j]--;
}
}
}
ans++;
}
cout<<--ans;
return 0;
}
本文链接:http://kaispace.com.cn/index.php/archives/532/
如果未注明出处,复制公开后需将注明本博客链接。打赏作者