P1983 [NOIP2013 普及组] 车站分级题解
这篇文章建立虚点我是没问题 但是建DAG图的时候连边要维护单调性吧
int vt=n+i;
for(int j=st;j<=ed;j++)
{
if(isin[j]==0)
{
g[j].push_back(vt);
rd[vt]++;
}
else
{
g[vt].push_back(j);
rd[j]++;
}
}
但是这边题解的代码不难发现他是一组只建立一个虚拟节点 那问题就在于根据题设的条件 假设三个数据是 x,y,z ,y 不停靠且 x,z 停靠当且仅当
y<x≤z 但是这边的 x 仅是不停靠区段最左相邻的一个车站 k 的等级,而在这个车站 k 的左侧被停靠的车站在等级上完全可以小于或者等于车站 k 的等级,那如何保证 车站 y 和车站 k 左侧车站连边后全图的偏序性呢