[洛谷 5603]小C与桌游

题目链接

https://www.luogu.org/problem/P5603

题解

对于每次都能得筹码的情况，我们每次只需贪心选当前能走到的点中编号最小的点即可。这个可以很轻松地用拓扑排序实现。

而对于每次都能失去筹码的情况，一种显然的想法是每次贪心地选当前能走到的点中编号最大的点。

然而这种做法是有问题的。一些编号较大的点可能因为其前置点编号过小而无法走到。

如果当前走过的点的最大编号为 \(maxx\)，如果目前能走的点中存在编号小于 \(maxx\) 的点，我们很显然可以先走这些点（先走这些点不会让答案变劣）。

假如不存在这样的点呢？那我们再按之前的思路取编号最大的点走就行了。

#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
using namespace std;
struct edge
{
 int v,next;
}e[500005];
int head[500005],t[500005],n,m,cnt;
void addedge(int u,int v)
{
 e[++cnt].v=v;
 e[cnt].next=head[u];
 head[u]=cnt;
}
namespace p1
{
 int in[500005];
 priority_queue<int,vector<int>,greater<int> >q;
 void solve()
 {
  memcpy(in,t,sizeof(t));
  for(int i=1;i<=n;i++)
   if(!in[i])q.push(i);
  int maxp=0,ans=0;
  while(!q.empty())
  {
   int u=q.top();
   q.pop();
   if(u>maxp)ans++,maxp=u;
   for(int i=head[u];i;i=e[i].next)
   {
    int v=e[i].v;
    in[v]--;
    if(!in[v])q.push(v);
   }
  }
  printf("%d\n",ans);
 }
}
namespace p2
{
 int in[500005];
 set<int> s;
 void solve()
 {
  memcpy(in,t,sizeof(t));
  for(int i=1;i<=n;i++)
   if(!in[i])s.insert(i);
  int maxp=0,ans=0;
  while(!s.empty())
  {
   int u;
   if(maxp>*s.begin())
   {
    u=*s.begin();
    s.erase(u);
   }
   else
   {
    auto it=s.end();
    it--;
    u=*it;
    s.erase(u);
   }
   if(u>maxp)ans++,maxp=u;
   for(int i=head[u];i;i=e[i].next)
   {
    int v=e[i].v;
    in[v]--;
    if(!in[v])s.insert(v);
   }
  }
  printf("%d\n",ans);
 }
}
int main()
{
 scanf("%d%d",&n,&m);
 for(int i=1;i<=m;i++)
 {
  int u,v;
  scanf("%d%d",&u,&v);
  addedge(u,v);
  t[v]++;
 }
 p1::solve();
 p2::solve();
 return 0;
}