题目:
小Z和小T正在van游戏。
有一张n个节点m条边的有向图,第i个节点的权值为ai。小T初始在某个节点上放着一枚棋子。每一回合小T有两种选择:
-
不移动棋子。
-
选择棋子所在节点的一条出边并将棋子移动到指向的那个节点。
每一回合之前小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次
由于目前的值是最大的,所以能断边的就要立即断
实际上就是一个贪心了
代码很短,关键是思维要跳脱出来
#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