【题解】[HNOI2015]菜肴制作(贪心+topo序)
题意:请你构造一个排列\(p[i]\)使得对于数组\(arc[i]=p[i]\)的字典序最小,并且对于给定的有序数对\((u,v)\)保证你给出的排列\(u\)早于\(v\)出现。
结论:\(u->v\)连边的反图的最大拓扑序的reverse
证明:这个排列的合法性是显然的,因为是topo序。下证不存在一个更优排列\(p[]\)使得\(arc[]\)字典序更小。
考虑反证,假设存在一个更优排列\(p'[]\)比我们如上算法得到的\(p[]\)要更优。
不妨假设\(p\not = p'\)
下证\(r'=\mathrm{reverse}(p')\)必然是反图拓扑序的一组解,否则\(p'\)必不是一组合法解。
证明:显然由于\(p'\)满足了题意条件,也就是满足\(u\)在\(v\)前出现,那么将\(r'\),就满足\(u\)在\(v\)后出现。所以\(r'\)将是一组反图拓扑序合法解。
所以\(r'\)可以跑反图拓扑序得到,设\(r=\mathrm{reverse}(p)\)。设\(\min i,\mathrm{s.t.} arc[i]>arc'[i]\),
那么肯定更优不会证明了记住套路吧
这是一类题,要你通过构造排列\(p\)使得\(\mathrm{arc}\ p\)的字典序最小。
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define DEBUG(s)
using namespace std; typedef long long ll;
inline int qr(){
register int ret=0,f=0;
register char c=getchar();
while(!isdigit(c))f|=c==45,c=getchar();
while(isdigit(c)) ret=ret*10+c-48,c=getchar();
return f?-ret:ret;
}
vector<vector<int> > e;
vector<int> dr,ans;
priority_queue<int,vector<int>,greater<int> > q;
int n,m;
inline void add(const int&fr,const int&to){
//DEBUG(fr); DEBUG(to);
e[to].push_back(fr); ++dr[fr];
}
inline void work(){
n=qr(); m=qr();
e.clear(); e.resize(n+1); dr.clear(); dr.resize(n+1); ans.clear();
//DEBUG(n); DEBUG(m);
for(int t=1;t<=n;++t) if(dr[t]) cerr<<"wa";
for(int t=1,x,y;t<=m;++t){
x=qr(),y=qr();
add(y,x);
}
for(int t=1;t<=n;++t) if(!dr[t]) q.push(t);
while(q.size()){
int now=q.top();
q.pop();
//DEBUG(now);
ans.push_back(now);
for(const auto&t:e[now])
if(--dr[t]==0)
q.push(t);
}
if((int)ans.size()!=n) return puts("Impossible!"),void();
for(const auto&t:ans)
printf("%d ",t);
putchar('\n');
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
//freopen("debug.out","w",stderr);
int T=qr();
while(T--) work();
return 0;
}