USACO18OPEN GOLD Milking Order

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Mon Sep 17 09:37:06 CST 2018

In Category: NoCategory

Description：

给出 $m$ 条类似于 $a[w[i][1]]<a[w[i][2]]<a[w[i][3]]<\cdots<a[w[i][k]]$ 的限制，满足尽量多的前缀限制，并输出一个字典序最小的方案。

$1\le n \le 100000,1\le m \le 50000$

Solution：

先二分一个值 $x$ ，然后判断 $1\sim x$ 的条件能否被同时满足，这个拓扑排序或者 $\text{tarjan}$ 都可以，最后输出方案的时候把拓扑排序的时候用的容器改成小根堆就能保证字典序最小了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<vector>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int ind[MAXN];

struct edge

{

	int to,nxt;

}e[200010];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

	++ind[b];

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

#define MAXM 50010

vector<int> g[MAXM];

inline bool check(int p)

{

	memset(lin,0,sizeof(lin));

	edgenum = 0;

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

	for(register int i = 1;i <= p;++i)

		for(register int j = 1;j < g[i].size();++j)

			add(g[i][j - 1],g[i][j]);

	queue<int> q;

	for(register int i = 1;i <= n;++i)

		if(ind[i] == 0)

			q.push(i);

	while(!q.empty())

	{

		register int k = q.front();q.pop();

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

		{

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

			if(ind[e[i].to] == 0)

				q.push(e[i].to);

		}

	}

	for(register int i = 1;i <= n;++i)

		if(ind[i] != 0)

			return false;

	return true;

}

inline void print(int p)

{

	memset(lin,0,sizeof(lin));

	edgenum = 0;

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

	for(register int i = 1;i <= p;++i)

		for(register int j = 1;j < g[i].size();++j)

			add(g[i][j - 1],g[i][j]);

	priority_queue<int,vector<int>,greater<int> > q;

	for(register int i = 1;i <= n;++i)

		if(ind[i] == 0)

			q.push(i);

	while(!q.empty())

	{

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

		printf("%d ",k);

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

		{

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

			if(ind[e[i].to] == 0)

				q.push(e[i].to);

		}

	}

	puts("");

	return;

}

int main()

{

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

	register int s,k;

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

	{

		s = read();

		for(int j = 1;j <= s;++j)

		{

			k = read();

			g[i].push_back(k);

		}

	}

	register int l = 1,r = m,mid;

	while(l < r)

	{

		mid = (l + r + 1) >> 1;

		if(check(mid))l = mid;

		else r = mid - 1;

	}

	print(l);

	return 0;

}

In tag: 算法-二分图论-拓扑排序

wjh15101051