[Acwing] 456. 车站分级 差分约束+拓扑排序

前言

传送门 :

思路

题目中 描述所有级别大于等于 x x x的车站必须停靠

因此可得,所有停靠车站的级别一定 > = >= >=未停靠的车站

因此分析题目,显然是一个差分约束的题

对于 a > b a>b a>b的关系我们需要 b − > a , w = 1 b->a,w=1 b−>a,w=1

存放拓扑图这个操作骚到我了

Mycode

const int N = 2010,M = 1e6+10;

int n,m;
int h[N],e[M],ne[M],w[M],idx;
int q[N],d[N];
int dist[N];
bool st[N];

void add(int a,int b,int c){
	e[idx] = b , w[idx] = c ,ne[idx] = h[a],h[a]=idx++;
	d[b]++;
}
void topsort(){
	int hh =0  ,tt =-1;
	for(int i=1;in>>m;
	for(int i=1;i>cnt;
		
		int start = n , end = 1;
		while(cnt -- ){
			int stop;cin>>stop;
			start = min(start,stop);
			end = max(end,stop);
			st[stop] = 1;
		}
		
		int ver = n+i;
		for(int j = start;j