【题解】[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;

}

巴特西

【题解】[HNOI2015]菜肴制作(贪心+topo序)

【题解】[HNOI2015]菜肴制作(贪心+topo序)

最新文章

热门文章