【20WC集训】van游戏

题目:

 

小Z和小T正在van游戏。

有一张n个节点m条边的有向图,第i个节点的权值为ai。小T初始在某个节点上放着一枚棋子。每一回合小T有两种选择:

  1. 不移动棋子。

  2. 选择棋子所在节点的一条出边并将棋子移动到指向的那个节点。

每一回合之前小ZZ可以选择至多KK条出边,这一回合小T就无法选择那些出边了。

这个游戏一共有10^100个回合,最终棋子所在的节点的权值即为小T的得分。小T想要得分尽量大,小Z想要小T的得分尽量小。假设小Z和小T都使用最优策略,请你计算出以每个节点为初始节点时,最终小T的得分是多少。


输入格式

第一行三个整数n,m,K。

第二行n个整数,表示节点的权值。

接下来每行两个整数x,y,表示一条x到y的有向边。

输出格式

输出n行,第i行表示以第i个节点作为初始节点时游戏最终小T的得分。


样例

input

4 6 1
4 3 2 1
1 4
2 1
3 1
3 2
4 2
4 3

output

4
3
3
3

explanation

假设以4号节点作为起点,由于4号节点有两条出边,所以小T可以将棋子移到2号节点或者3号节点。

而对于3号节点小Z需要指定小T不可以使用到达1号点的出边,所以小T也可以从3号节点移动到2号节点。

无论哪种情况小T都可以到达2号节点,最终获得3分。


数据规模与约定

保证图中没有自环。但是可能会存在重边。

1≤n≤10^5, m≤5n, 0≤K≤n, 0≤ai≤10^9

  • Subtask1(8%):n≤10

  • Subtask2(22%):保证给定图是有向无环图,且有向边只会从编号小的点指向编号大的点

  • Subtask3(17%):K=0

  • Subtask4(19%):n≤1000

  • Subtask5(14%):ai≤1

  • Subtask6(20%):无特殊限制

时间限制:1s

空间限制:512MB

 

分析:

 先想的是正着做,由于回合数很多,所以除非小Z阻挡,小T一定能够走到所有点

那么走到每一个点时,小Z要做的就是将出边所有能够到的前K大的值的方案给阻挡住

这样在无环的情况下是显然可做的

可是有环的时候就无法解决了

难受。。。

然后正着没法做,考虑一下反着做

考虑每个点的值可以贡献到哪些点。。。

诶?一下子就很简单了

建一个反向图,将点按点值从大到小排序

考虑一个一个加入值

由于目前加入的值肯定不会更新已经有答案的点

所以每个点只会被刷新一次

作为小Z,你肯定不想目前最大的值在图上未被刷新的电上扩散

这时要做的就不是断出边而是断入边了,每个点最多被断K次

由于目前的值是最大的,所以能断边的就要立即断

实际上就是一个贪心了

代码很短,关键是思维要跳脱出来

【20WC集训】van游戏
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>

#define maxn 1000005

using namespace std;

inline int getint()
{
    int num=0,flag=1;char c;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
    while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
    return num*flag;
}

int n,m,K;
int fir[maxn],nxt[maxn],to[maxn],cnt;
int Lim[maxn],ans[maxn];
struct node{
    int val,u;
}P[maxn];
inline bool cmp(node x,node y){return x.val>y.val;}

inline void newnode(int u,int v)
{to[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;}

inline void dfs(int u,int num)
{
    ans[u]=num;
    for(int i=fir[u];i;i=nxt[i])
        if(!~ans[to[i]])
        {
            if(Lim[to[i]])Lim[to[i]]--;
            else dfs(to[i],num);
        }
}

int main()
{
    memset(ans,-1,sizeof ans);
    n=getint(),m=getint(),K=getint();
    for(int i=1;i<=n;i++)Lim[i]=K;
    for(int i=1;i<=n;i++)P[i].u=i,P[i].val=getint();
    for(int i=1;i<=m;i++)
    {
        int u=getint(),v=getint();
        newnode(v,u);
    }
    sort(P+1,P+n+1,cmp);
    for(int i=1;i<=n;i++)if(!~ans[P[i].u])dfs(P[i].u,P[i].val);
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
}
View Code

【20WC集训】van游戏

上一篇:python os模块获取指定目录下的文件列表


下一篇:封装van-popup为自己的弹窗组件解决v-moel props单向数据流不能修改的问题。