目录
显示
题目链接
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;
}
#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;
}
#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; }