对于题解的疑问
查看原帖
对于题解的疑问
1377813
Luo_Saisei楼主2025/7/24 16:32

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,zx,y,z ,yy 不停靠且 x,zx,z 停靠当且仅当 y<xzy<x\le z 但是这边的 xx 仅是不停靠区段最左相邻的一个车站 kk 的等级,而在这个车站 kk 的左侧被停靠的车站在等级上完全可以小于或者等于车站 kk 的等级,那如何保证 车站 yy 和车站 kk 左侧车站连边后全图的偏序性呢

2025/7/24 16:32
加载中...