车站分级——拓扑排序的应用(虚拟节点)
原题链接:https://www.acwing.com/problem/content/458/
思路:(分析一下是怎么想到的拓扑排序的)
首先,拓扑排序的应用条件是有向无环图,由题目中描述的内容**“如果这趟车次停靠了火车站 x,则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠”** 易知,利用了拓扑排序的思想~
具体怎么利用了呢?
由题意可知:所有没有停靠的站点的级别,一定小于所有停靠的站点的级别,也就是说,可以建立一个大小关系,而这个大小关系是一个有向无环图!
好了,既然知道了要用到拓扑排序,那么要怎么用呢?
首先,先建图!
但是,这个题目的数据,摆明了不想让我们好好建图,那我们就要用到一个虚拟结点的思想!!!
简单来说就是,左边一堆结点,都指向右边的一堆结点,那么肯定有n*m条边,那我们不妨在它们中间加上一个虚拟结点,作为“中转点”,左边的结点通过指向中转点,再指向右边的点!!!这样一来,就变成了 n+m 条边!!!
注意,由于权重不能变,所以不妨设,左边指向虚拟节点的权重为0,虚拟结点指向右边的权重为1。
cin>>n>>m;
for(int i = 1;i<=m;i++)
{
memset(st,0,sizeof st);
int tmp = 0;
int start=n,end=1;
cin>>x;
while(x--)
{
cin>>tmp;
start = min(start,tmp);
end = max(end,tmp);
st[tmp] = 1;
}
//虚拟结点
//建图
int ver = i+n;
for(int j = start;j<=end;j++)
{
if(!st[j])
{
v[j].push_back({
ver,0});
d[ver]++;
}
else
{
v[ver].push_back({
j,1});
d[j]++;
}
}
}
建好图之后,我们就要利用拓扑排序的思想了~
模板类的,就不详细介绍了~
//拓扑排序
void topsort()
{
queue<int> q;
for(int i = 1;i<=n+m;i++)
{
if(d[i]==0)
{
q.push(i);
top[++num] = i;
}
}
while(!q.empty())
{
int x = q.front();
q.pop();
for(int i = 0;i<v[x].size();i++)
{
int j = v[x][i].first;
if(--d[j]==0)
{
q.push(j);
top[++num] = j;
}
}
}
}
拓扑排序之后,我们可以确定,数组top中,前面的元素车站级别肯定小于等于后面的
于是乎:
for(int i = 1;i<=num;i++)
{
int x = top[i];
for(int j = 0;j<v[x].size();j++)
{
int u = v[x][j].first;
int len = v[x][j].second;
//拓扑排序后的,后面的车站等级要大于等于前面的
dist[u] = max(dist[u],dist[x] + len);
}
}
int res = 0;
for(int i = 1;i<=n;i++)
{
res = max(res,dist[i]);
}
cout<<res<<"\n";
注意这里的dist数组的意思是,每个车站的级别
所以需要初始化:
for(int i = 1;i<=n;i++)
dist[i] = 1; //每个车站的最小等级为 1
完整代码
#include<bits/stdc++.h>
#define N 10100
using namespace std;
typedef pair<int,int> PII;
vector<PII> v[N];
int n,m;
bool st[N];
int d[N];
int dist[N];
int num;
int top[N];
//拓扑排序
void topsort()
{
queue<int> q;
for(int i = 1;i<=n+m;i++)
{
if(d[i]==0)
{
q.push(i);
top[++num] = i;
}
}
while(!q.empty())
{
int x = q.front();
q.pop();
for(int i = 0;i<v[x].size();i++)
{
int j = v[x][i].first;
if(--d[j]==0)
{
q.push(j);
top[++num] = j;
}
}
}
}
int main()
{
int x=0;
cin>>n>>m;
for(int i = 1;i<=m;i++)
{
memset(st,0,sizeof st);
int tmp = 0;
int start=n,end=1;
cin>>x;
while(x--)
{
cin>>tmp;
start = min(start,tmp);
end = max(end,tmp);
st[tmp] = 1;
}
//虚拟结点
//建图
int ver = i+n;
for(int j = start;j<=end;j++)
{
if(!st[j])
{
v[j].push_back({
ver,0});
d[ver]++;
}
else
{
v[ver].push_back({
j,1});
d[j]++;
}
}
}
topsort();
for(int i = 1;i<=n;i++)
dist[i] = 1; //每个车站的最小等级为 1
for(int i = 1;i<=num;i++)
{
int x = top[i];
for(int j = 0;j<v[x].size();j++)
{
int u = v[x][j].first;
int len = v[x][j].second;
//拓扑排序后的,后面的车站等级要大于等于前面的
dist[u] = max(dist[u],dist[x] + len);
}
}
int res = 0;
for(int i = 1;i<=n;i++)
{
res = max(res,dist[i]);
}
cout<<res<<"\n";
return 0;
}
文章评论