首页 > 其他分享 >Game On Graph

Game On Graph

时间：2023-03-11 13:15:24浏览次数：36  
标签：ch int Graph 入队 read Game include define

最近总是见到在有向图上面移棋子的博弈论题，都是如果把有向图换成 DAG 就很 naive 的，核心问题都在于如何处理环，所以来记一记。

  1. Alice 负责走棋子，在 Alice 走之前 Bob 可以封住至多 \(K\) 条出边，得分为最终到的棋子的点权，Alice 想让得分大，Bob 想让得分小，对于每个起点求最终得分。Alice 可以选择结束游戏。

\(f_i\) 表示从 \(i\) 出发的最终得分，如果是 DAG 就很好处理，有环的话我们可以考虑 dij，因为 \(f\) 满足最短路的性质，只会从大转移到小。发现 Bob 只会封掉前 \(K\) 大，而 dij 出队的顺序是从大到小，所以反向建图，当一个点被第 \(K+1\) 次松弛的时候更新。

#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<queue>
#include<vector>
#define N 100005
using namespace std;
inline int read(){
	int x=0,f=0; char ch=getchar();
	while(!isdigit(ch)) f|=(ch==45),ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
int n,m,k,a[N],mx,f[N],vis[N],cnt[N];
priority_queue<pair<int,int> > q;
vector<int> G[N];
int main(){
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;++i) a[i]=read(),mx=max(mx,a[i]);
	for(int i=1;i<=m;++i){
		int x=read(),y=read();
		G[y].push_back(x);
	}
	for(int i=1;i<=n;++i){
		f[i]=a[i];
		q.push({f[i],i});
	}
	while(!q.empty()){
		int u=q.top().second;q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int v:G[u]){
			cnt[v]++;
			if(cnt[v]==k+1){
				if(f[u]>f[v]){
					f[v]=f[u];
					q.push({f[v],v});
				}
			}
		}
	}
	for(int i=1;i<=n;++i) printf("%d\n",f[i]);
	return 0;
}
  1. 有向图上两人交替移石子，\(i\) 号点的点权为 \(i\)，Alice 先手，得分是路径上点权的最大值，Alice 想让得分大，Bob 想让得分小，游戏进行 \(114^{514}\) 轮，无法行动则游戏结束。

考虑 dij，\(f_u,g_u\) 分别代表先手/后手在点 \(u\) 出发的最终得分，一开始 \(f_u=g_u=u\)，所有点入队，然后一个一个一个出队，出队顺序为从大到小。建反图，然后我们钦定从 \(g\) 转移到 \(f\) 时只要松弛到了就入队，从 \(f\) 转移到 \(g\) 时只有转移完了所有边才入队，注意到一个细节：一个点如果可以走出去是必须走出去的，这样导致了 \(f\) 转移到 \(g\) 时，可以只有最后一次松弛的时候才更新，就不取 min 了（dij 的出队顺序从大到小）。

分析这样为什么是对的，核心思路是 dij 的里出来的数是从大到小的，这样导致每次拿出来的队头的结果都是正确的：如果队头是 \(f\)，因为它是最大的，队列里面的都不会比他大，也就是松弛不到它；如果队头是 \(g\)，它入队的时候肯定是被所有出边都松弛过了，这样它也是完全松弛好的。但是可能 \(g\) 还没有被所有出边松弛好，这个入队是一开始所有点入队那里入的，那肯定没有松弛到它的出边的 \(f\) 肯定小于 \(u\)，和 \(u\) 取 max 之后结果肯定是 \(u\)，且 \(g\) 是想让得分小，只要往没松弛到 \(u\) 的出边那里走就可以实现得分等于 \(u\)。所以这时 \(g_u=u\)，而我们一开始的 \(g_u\) 全部等于了 \(u\)，所以是正确的。

#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<queue>
#define N 100005
#define ll long long
#define ld long double
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&-(x))
#define popcount(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define umap unordered_map
#define all(x) x.begin(),x.end()
#define mk make_pair
#define ckmax(x,y) x=max(x,y)
#define ckmin(x,y) x=min(x,y)
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define N 100005
using namespace std;
inline int read(){
	int x=0,f=0; char ch=getchar();
	while(!isdigit(ch)) f|=(ch==45),ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
struct edge{
	int b,n;
}e[N*2];
int n,m,h[N],tot,f[2*N],in[N],vis[2*N];
priority_queue<pii> q;
inline void charu(int a,int b){
	e[++tot].b=b,e[tot].n=h[a],h[a]=tot;
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=m;++i){
		int x=read(),y=read();
		charu(y,x);
		in[x]++;
	}
	for(int i=1;i<=n;++i){
		f[i]=f[i+n]=i;
		q.push({f[i],i}),q.push({f[i+n],i+n});
	}
	while(!q.empty()){
		int u=q.top().se;q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		if(u>n){
			u-=n;
			for(int i=h[u];i;i=e[i].n){
				int v=e[i].b;
				if(f[u+n]>f[v]){
					f[v]=f[u+n];
					q.push({f[v],v});
				}
			}
		}
		else{
			for(int i=h[u];i;i=e[i].n){
				int v=e[i].b;
				--in[v];
				if(!in[v]){
					if(f[u]>f[v+n]){
						f[v+n]=f[u];
						if(!in[v]){
							q.push({f[v+n],v+n});
						}
					}
				}
			}
		}
	}
	for(int i=1;i<=n;++i) printf("%d ",f[i]);
	return 0;
}
  1. (ABC261EX)有向图上两人交替移棋子，Alice 先手，得分为路径边权和，Alice 想让得分小，Bob 想让得分大，求最终得分，如果游戏不会结束输出 INF。

恶心的地方在于 INF，考虑一个简化版的题面：Alice 想让游戏结束，Bob 不想让游戏结束，求最后会不会结束。\(f_u,g_u\) 分别表示先手/后手从 \(u\) 开始游戏会不会结束。出度为 0 的节点显然游戏会结束，考虑上一题类似的方法，游戏会结束的状态才入队，那这样 \(f\) 只要被更新到就入队，\(g\) 只有被所有出边松弛到才入队。发现入过队的状态就是游戏会结束的状态！

然后把边权的问题加回来，其实把 \(f,g\) 的定义改成最小的最大就可以了，还是没有入过队的状态是 INF，出队顺序改成从小到大。

#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<queue>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&-(x))
#define popcount(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define umap unordered_map
#define all(x) x.begin(),x.end()
#define mk make_pair
#define ckmax(x,y) x=max(x,y)
#define ckmin(x,y) x=min(x,y)
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define N 200005
#define int long long
using namespace std;
inline int read(){
	int x=0,f=0; char ch=getchar();
	while(!isdigit(ch)) f|=(ch==45),ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
struct edge{
	int b,c,n;
}e[N*2];
int n,m,s,h[N],tot,in[N],f[2*N],vis[2*N];
priority_queue<pii> q;
inline void charu(int a,int b,int c){
	e[++tot].b=b,e[tot].c=c,e[tot].n=h[a],h[a]=tot;
}
signed main(){
	n=read(),m=read(),s=read();
	for(int i=1;i<=m;++i){
		int x=read(),y=read(),z=read();
		charu(y,x,z);
		in[x]++;
	}
	for(int i=1;i<=n;++i) f[i]=infll;
	for(int i=1;i<=n;++i) if(!in[i]) f[i]=0,q.push({0,i}),q.push({0,i+n});
	while(!q.empty()){
		int u=q.top().se;q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		if(u>n){
			u-=n;
			for(int i=h[u];i;i=e[i].n){
				int v=e[i].b;
				if(f[u+n]+e[i].c<f[v]){
					f[v]=f[u+n]+e[i].c;
					q.push({-f[v],v});
				}
			}
		}
		else{
			for(int i=h[u];i;i=e[i].n){
				int v=e[i].b;
				in[v]--;
				f[v+n]=max(f[v+n],f[u]+e[i].c);
				if(!in[v]) q.push({-f[v+n],v+n});
			}
		}
	}
	if(!vis[s]) puts("INFINITY");
	else printf("%lld",f[s]);
	return 0;
}

发现上面两题的做法很相似，但是其实做法的思想差别很大，做法为什么对的原因也不太一样。所以还是要具体问题具体分析。

还有就是堆是小根堆还是大根堆的问题，这个要考虑初始状态，如果初始状态是最小值就用小根堆，反之用大根堆。知道了出队顺序之后就可以简单的确定先手后手哪个一被更新就入队，哪个所有出边被松弛才入队。

  1. (NEERC2016)有向图上交替移石子，无法行动者输，第一个人最希望平局，其次希望赢，最不希望输，第二个人最希望赢，其次希望输，最不希望平局。平局指游戏永远不会结束。

发现两个人都是先确定是否会平局的情况下再尽可能地取赢，所以我们可以使用上一题中的方法求出每个点出发是否会平局。

之后我们可以做一个普通的拓扑来转移胜负，就是一个状态如果能到一个败就是胜，否则是败。

然而这样会有些状态转移不到，出现这样的情况就说明有环，但是又没有平局，说明这个人用策略避免了走环，所以这是第二个人的状态。如果他避免了走环切又赢了，这个状态就应该被更新到了（因为出现一个能到的败状态就会更新），所以这个状态啊应该是必败，也就是说在这个状态第二个人为了避免平局而选择了败。

但是我们不好把这些状态再加入队列，所以就不加了，因为发现它只会更新到它直接相连的状态，所以最后没访问到的第二个人的状态直接是必败，没访问到的第一个人的状态直接是必胜。

#include<cstdio>
#include<vector>
#include<queue>
const int N=100010;
std::vector<int>g[N],gr[N];
std::queue<std::pair<int,int>>q;
int n,m,drw[N][2],win[N][2],du[N],dt[N],d[N][2];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),
	g[x].push_back(y),gr[y].push_back(x),++du[x];
	for(int i=1;i<=n;i++)
	{
		if(!du[i])q.emplace(i,0),q.emplace(i,1);
		else drw[i][0]=drw[i][1]=1;
		dt[i]=du[i];
	}
	while(!q.empty())
	{
		int u=q.front().first,p=q.front().second;q.pop();
		for(int v:gr[u])
		if((p==0&&drw[v][1])||(p==1&&!--dt[v]))
		drw[v][p^1]=0,q.emplace(v,p^1);
	}
	for(int i=1;i<=n;i++)
	{
		if(!du[i])q.emplace(i,0),q.emplace(i,1);
		else win[i][0]=win[i][1]=-1;
		for(int v:g[i])d[i][0]+=!drw[v][1],d[i][1]+=!drw[v][0];
	}
	while(!q.empty())
	{
		int u=q.front().first,p=q.front().second;q.pop();
		for(int v:gr[u])if(!drw[v][p^1])
		if(win[u][p]){if(!--d[v][p^1])q.emplace(v,p^1),win[v][p^1]=0;}
		else {if(win[v][p^1]==-1)q.emplace(v,p^1),win[v][p^1]=1;}
	}
	for(int i=1;i<=n;i++)(win[i][0]==-1)&&(win[i][0]=1),(win[i][1]==-1)&&(win[i][1]=0);
	for(int i=1;i<=n;i++)putchar(drw[i][0]?'D':(win[i][0]?'W':'L'));putchar('\n');
	for(int i=1;i<=n;i++)putchar(drw[i][1]?'D':(win[i][1]?'W':'L'));putchar('\n');
	return 0;
}

标签：ch,int,Graph,入队,read,Game,include,define
From： https://www.cnblogs.com/xzzduang/p/17205691.html

相关文章

  • A. Stone Game
    A.StoneGame代码点击查看代码#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intmain(){ intt; cin>>t; while(t--){ ......
  • LightGCL: Simple Yet Effective Graph Contrastive Learning for Recommendation
    目录概符号说明基本流程模型的基本流程另一个View优化代码CaiX.,HuangC.,XiaL.andRenX.LightGCL:Simpleyeteffectivegraphcontrastivelearningforreco......
  • A. Computer Game【dfs诈骗】
    A.ComputerGame代码点击查看代码#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#include<queue......
  • Games101-Cp1-Transformation
    最近为了求职重新开始把图形学相关的内容重新系统的学习，先把Games101的内容入门，然后把虎书相关的内容补充。Transformation矩阵变换可以对不同坐标系之间进行转换，在这个......
  • AmpliGraph1.4 使用记录
    参考官方文档：https://docs.ampligraph.org/en/1.4.0/index.html由于笔者的电脑装最新的Ampligrah2.0时总会报错，所以装的老版本1.4。安装：conda、CUDA和CUDnn的安......
  • 一文上手图数据备份恢复工具 NebulaGraph BR
    作者：NebulaGraph工程师KenshinNebulaGraphBR开源已经有一段时间了，为了给社区用户提供一个更稳、更快、更易用的备份恢复工具，去年对其进行了比较大的重构。NebulaGr......
  • CF207C3 Game with Two Trees 题解
    脑子不够，科技来凑。不过好像也没有用多么高级的科技……首先这个题目很坏，它让你翻转\(S_{t_2}\)。即从\(t_2\)某个节点往下走到另一个节点的路径所表示的字符串。这个......
  • CF1796E Colored Subgraphs
    个人思路：换根。从\(1\)开始DFS遍历。对于一个点，维护\(mx1_u=\min\limits_{v\inchild_u}mx1_v+1\)，\(mx2_u\)为\(\min\limits_{v\inchild_u}mx2_v\)和\(m......
  • AgensGraph语法
    1、创建数据库、用户、图--cmd连接数据库psql-Uagens-p5432--创建数据库createdatabasencxauth;--创建用户createuserncxauthwithpassword'ncxauth';--......
  • DelegateAuthenticationProvider not found after updating Microsoft Graph
    c#-DelegateAuthenticationProvidernotfoundafterupdatingMicrosoftGraph-StackOverflow回答msgraph-sdk-dotnet/upgrade-to-v5.mdatfeature/5.0·micros......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99