bzoj5280/luogu4376 MilkingOrder (二分答案+拓扑序)

二分答案建图,然后判环,就可以了。

字典序输出的话,只要做拓扑序的时候用优先队列来维护就可以了。

(其实判环也可以用拓扑序...)

 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<ctime>
#define LL long long
using namespace std;
const int maxn=,maxm=,summ=; LL rd(){
LL x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,M;
int eg[summ][],egh[maxn],ect,ine[maxn];
bool flag[maxn],instk[maxn],ans; inline void adeg(int a,int b,int m){
eg[++ect][]=b;eg[ect][]=egh[a];eg[ect][]=m;egh[a]=ect;
} bool dfs(int x,int m){
flag[x]=instk[x]=;bool re=;
for(int i=egh[x];i!=-;i=eg[i][]){
if(eg[i][]>m) continue;
if(!flag[eg[i][]]) re|=dfs(eg[i][],m);
else if(instk[eg[i][]]) return ;
}instk[x]=;return re;
} int main(){
//freopen("4376.in","r",stdin);
int i,j,k;
N=rd(),M=rd();memset(egh,-,sizeof(egh));
for(i=;i<=M;i++){int last=;
for(j=rd();j;j--){
k=rd();if(last) adeg(last,k,i);last=k;
}
}
int l=,r=M;
while(l<=r){
memset(instk,,sizeof(instk));memset(flag,,sizeof(flag));
int m=l+r>>;bool b=;
for(i=;i<=N;i++) if(!flag[i]) b|=dfs(i,m);
if(b) r=m-;
else{
l=m+;
}
}l--;
for(i=;i<=ect;i++){
if(eg[i][]<=l) ine[eg[i][]]++;
}priority_queue<int,vector<int>,greater<int> > q;
for(i=;i<=N;i++) if(!ine[i]) q.push(i);
while(!q.empty()){
int p=q.top();q.pop();printf("%d ",p);
for(i=egh[p];i!=-;i=eg[i][]){
if(eg[i][]>l) continue;
int b=eg[i][];ine[b]--;
if(!ine[b]) q.push(b);
}
}
return ;
}
上一篇:mysql锁死的现象判断


下一篇:背水一战 Windows 10 (72) - 控件(控件基类): UIElement - UIElement 的位置, UIElement 的布局, UIElement 的其他特性