NOI2010 航空管制

wjh15101051's space

卧薪尝胆，厚积薄发。

NOI2010 航空管制

Date: Wed Mar 20 09:06:34 CST 2019

In Category: NoCategory

Description：

给出一些限制，每个限制形如 $a$ 的序号不能超过 $k_a$ 或者 $a$ 必须在 $b$ 之前，求出一组合法解并给出每个元素在所有方案中最靠前的位置。

$1\leqslant n\leqslant 2000,1\leqslant m\leqslant 100000$

Solution：

第一问比较好做，首先发现如果按照 $k_a$ 为关键字起飞都不能合法的话，那么就一定不合法了，也就是说我们需要让 $k_a$ 小的尽量先起飞，于是这题就是HNOI2015菜肴制作，建反图拓扑排序就行了。

第二问有点麻烦，还是在反图上考虑，我们在考虑这个点的时候，再做一次拓扑排序，如果他的入度为 $0$ 了也不把它加进去，而是等到有一个不满足 $k$ 的时候就必须把它加入了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 2010

int p[MAXN];

#define MAXM 100010

struct edge

{

	int to,nxt;

}e[MAXM];

int edgenum = 0;

int lin[MAXN] = {0};

int ind[MAXN];

void add(int a,int b)

{

	++ind[b];

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

int topo[MAXN];

int work(int s)

{

	priority_queue< pair<int,int> > q;

	memset(ind,0,sizeof(ind));

	for(int i = 1;i <= m;++i)++ind[e[i].to];

	for(int i = 1;i <= n;++i)if(ind[i] == 0 && i != s)q.push(make_pair(p[i],i));

	int tot = n;

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(p[k] < tot)return tot;

		--tot;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			--ind[e[i].to];

			if(ind[e[i].to] == 0 && e[i].to != s)q.push(make_pair(p[e[i].to],e[i].to));

		}

	}

	return tot;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&p[i]);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		add(b,a);

	}

	priority_queue< pair<int,int> > q;

	for(int i = 1;i <= n;++i)if(ind[i] == 0)q.push(make_pair(p[i],i));

	topo[0] = n;

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		topo[topo[0]--] = k;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			--ind[e[i].to];

			if(ind[e[i].to] == 0)q.push(make_pair(p[e[i].to],e[i].to));

		}

	}

	for(int i = 1;i <= n;++i)printf("%d ",topo[i]);puts("");

	for(int i = 1;i <= n;++i)printf("%d ",work(i));puts("");

	return 0;

}

In tag: 图论-拓扑排序

wjh15101051