洛谷P4376 [USACO18OPEN] Milking Order G

洛谷题目传送门

题目描述

Farmer John 的 N 头奶牛（1≤N≤），编号为 1…N，最近闲得发慌。因此，她们发展了一个与 Farmer John 每天早上为她们挤牛奶时的排队顺序相关的复杂社会阶层。

经过若干周的研究，Farmer John 对他的奶牛的社会结构总计进行了 M 次观察（1≤M≤50,000）。每个观察结果都是某些奶牛的一个有序序列，表示这些奶牛应该按照序列中的顺序进行挤奶。例如，如果 Farmer John 的一次观察结果是序列 2、5、1，那么 Farmer John 应该在给奶牛 5 挤奶之前的某个时刻给奶牛 2 挤奶，并在给奶牛 1 挤奶之前的某个时刻给奶牛 5 挤奶。

Farmer John 的观察结果是按优先级排列的，因此他的目标是最大化 X 的值，使得他的挤奶顺序能够符合前 X 个观察结果描述的状态。当多种挤奶顺序都能符合前 X 个状态时，Farmer John 遵循一个长期以来的传统——编号较小的奶牛的地位高于编号较大的奶牛，因此他会最先给编号最小的奶牛挤奶。更正式地说，如果有多个挤奶顺序符合这些状态，Farmer John 会采用字典序最小的那一个。挤奶顺序 x 的字典序比挤奶顺序 y 小，如果对于某个 j，xi​=yi​ 对所有 i<j 成立，并且 xj​<yj​（即这两个挤奶顺序到某个位置之前完全相同，而在该位置上 x 比 y 小）。

请帮助 Farmer John 确定给奶牛挤奶的最佳顺序。

输入格式

第一行包含 N 和 M。接下来的 M 行，每行描述了一个观察结果。第 i+1 行描述了观察结果 i，第一个数是观察结果中的奶牛数量 mi​，后面是一列 mi​ 个整数，给出这次观察中奶牛的顺序。所有 mi​ 的总和至多为 200,000。

输出格式

输出 N 个空格分隔的整数，表示一个 1…N 的排列，为 Farmer John 给他的奶牛们挤奶应该采用的顺序。

输入输出样例

输入

4 3
3 1 2 3
2 4 2
3 3 4 1

输出

1 4 2 3

说明/提示

在这个例子中，Farmer John 有四头奶牛，他的挤奶顺序应该满足以下规则：奶牛 1 在奶牛 2 之前、奶牛 2 在奶牛 3 之前（第一个观察结果），奶牛 4 在奶牛 2 之前（第二个观察结果），奶牛 3 在奶牛 4 之前、奶牛 4 在奶牛 1 之前（第三个观察结果）。前两个观察结果可以同时被满足，但 Farmer John 不能同时满足所有规则，因为这会要求奶牛 1 在奶牛 3 之前，同时奶牛 3 在奶牛 1 之前。

这意味着总共有两种可能的挤奶顺序：1 4 2 3 和 4 1 2 3，第一种是字典序较小的。

思路

70pts:

由于前 x 个是必须一起选的，我们先考虑什么情况下不可能满足所有的观察结果

对于每一个观察结果，后面的必须要等前面的挤完奶才能挤奶，这就像一个拓扑排序

那么很显然，有环的时候无法进行拓扑排序

而判环可以用 tarjan 算法实现，我们只需要判断强连通分量的数量是否等于经过的点的数量

因为一个点也算一个强连通分量

那我们只需要每次加边，如果当前这一种状态有环，那上一种状态为最优状态

此时我们只需要用拓扑排序求出结果就行了

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m;
int to[N],ne[N],h[N],tot=0,tim=0,dfn[N],low[N],co[N],col=0,js=0,jsn=0;
int preto[N],prene[N],preh[N],pretot;//前一个状态的链式前向星 
void add(int u,int v){
	tot++;to[tot]=v;ne[tot]=h[u];h[u]=tot;
}
stack<int>st;
int in[N],out[N];//统计入度出度 
int prein[N],preout[N];//前一个状态的入度出度 
void tarjan(int u){//tarjan 判环 
	dfn[u]=low[u]=++tim;
	st.push(u);
	jsn++;//jsn 统计经过的点的数量 
	for(int i=h[u];i;i=ne[i]){
		int v=to[i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!co[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		col++;co[u]=col;
		js++;//统计强连通分量的数量 
		while(st.top()!=u){
			co[st.top()]=col;
			st.pop();
		}
		st.pop();
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int l,x,pre,beg;cin>>l;
		js=jsn=tim=col=0;pretot=tot;
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(co,0,sizeof(co));//数据清空 
		memcpy(prein,in,sizeof(prein));
		memcpy(preout,out,sizeof(preout));
		memcpy(preto,to,sizeof(preto));
		memcpy(prene,ne,sizeof(prene));
		memcpy(preh,h,sizeof(preh));//继承状态 
		for(int i=1;i<=l;i++){
			cin>>x;
			if(i!=1){
				add(pre,x);in[x]++;//建边 
			}
			else beg=x;
			pre=x;
		}
		tarjan(beg);
		if(js!=jsn){//如果有环那上一种状态最优 
			memcpy(in,prein,sizeof(in));
			memcpy(out,preout,sizeof(out));
			memcpy(to,preto,sizeof(to));
			memcpy(ne,prene,sizeof(ne));
			memcpy(h,preh,sizeof(h));//回溯状态 
			tot=pretot;
			priority_queue<int,vector<int>,greater<int>>q;//使用小根堆保证字典序最小 
			for(int i=1;i<=n;i++)if(in[i]==0)q.push(i);
			while(!q.empty()){
				int u=q.top();q.pop();
				for(int i=h[u];i;i=ne[i]){
					int v=to[i];
					in[v]--;
					if(in[v]==0)q.push(v);
				}
				cout<<u<<' ';
			}//拓扑排序求出结果 
			return 0;
		}
	}
	return 0;
}

可是这种方法只能得70分

100pts:

我们考虑在 70 分的代码上进行优化

首先，我们每一个观察结果都要进行一次判环，那时间复杂度即为 O(n*m)

这个时间复杂度是不能接受的

如果我们的观察结果越多，就越容易出现环，也就是说是否有环具有单调性！！！

那我们就可以使用二分去枚举取的是前几个观察现象

那我们还需要解决一个问题：我们如何知道前 x 个观察现象的状态(主要是链式前向星的状态)

我们可以用一个数组保存加的边，再用一个数组保存第 x 个观察结果的最后一个边的编号

最后我们只需要用拓扑排序求出最优状态下的顺序就可以了

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m;
int to[N],ne[N],h[N],tot=0,tim=0,dfn[N],low[N],co[N],col=0,js=0,jsn=0;
struct S{
	int x,y;
}edge[N*4];
int en[N],o=0;
void add(int u,int v){
	tot++;to[tot]=v;ne[tot]=h[u];h[u]=tot;
}
stack<int>st;
int in[N],out[N];
void tarjan(int u){//tarjan 判环 
	dfn[u]=low[u]=++tim;
	st.push(u);
	jsn++;
	for(int i=h[u];i;i=ne[i]){
		int v=to[i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!co[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		col++;co[u]=col;
		js++;
		while(st.top()!=u){
			co[st.top()]=col;
			st.pop();
		}
		st.pop();
	}
}
bool check(int mid){//判断前 mid 个观察结果是否有环 
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(co,0,sizeof(co));
	memset(h,0,sizeof(h));
	memset(ne,0,sizeof(ne));
	memset(to,0,sizeof(to));js=jsn=tim=col=tot=0;
	for(int i=1;i<=en[mid];i++)add(edge[i].x,edge[i].y);
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	return js==jsn;
}
int find(int l,int r){
	if(l>=r)return l;
	if(r-l==1)return check(r)?r:l;
	int mid=(l+r)/2;
	if(check(mid))return find(mid,r);
	return find(l,mid-1);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int l,x,pre,beg;cin>>l;
		js=jsn=tim=col=0;pretot=tot;
		for(int j=1;j<=l;j++){
			cin>>x;
			if(j!=1){
				add(pre,x);edge[++o]={pre,x};//记录下每一条边 
			}
			else beg=x;
			pre=x;
		}
		en[i]=o;
	}
	int pos=find(1,m);
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(co,0,sizeof(co));
	memset(h,0,sizeof(h));
	memset(ne,0,sizeof(ne));
	memset(to,0,sizeof(to));js=jsn=tim=col=0;
	for(int i=1;i<=en[pos];i++){
		add(edge[i].x,edge[i].y);in[edge[i].y]++;
	}
	priority_queue<int,vector<int>,greater<int>>q;
	for(int i=1;i<=n;i++)if(in[i]==0)q.push(i);
	while(!q.empty()){
		int u=q.top();q.pop();
		for(int i=h[u];i;i=ne[i]){
			int v=to[i];
			in[v]--;
			if(in[v]==0)q.push(v);
		}
		cout<<u<<' ';
	}
	return 0;
}