门户网站界面设计,好看logo图片,黑彩网站建设运营,汕头房产网题目
给定t(t200)组样例#xff0c;
每次给定一个n(n300)个左边的点m(m300)个右边的点的二分图#xff0c;图无重边
所有边总量不超过5e5 初始时棋子可以被放置在任意一个点上#xff0c;
若被放置在左边#xff0c;则Alice先走#xff1b;被放置在右边200)组样例
每次给定一个n(n300)个左边的点m(m300)个右边的点的二分图图无重边
所有边总量不超过5e5 初始时棋子可以被放置在任意一个点上
若被放置在左边则Alice先走被放置在右边则Bob先走
每次可以选择一个当前点有出边的点走到那个点上如果当前点没有出边则游戏结束 Alice想访问所有点无数次Bob想阻止Alice这么做双方均采取最优策略
问Alice是否有必胜策略Alice可以指定起点在哪里
思路来源
heltion蔡老师
题解
问题等价于
只要Bob能找到一个点使Alice不能无限次经过则Bob胜否则Alice胜
称这样的点为防御点 n300所以考虑枚举防御点
对于枚举的防御点先判断一下可达性如果有点到不了防御点则Alice全局必败 防御点是一个终态点如果Alice不能到防御点则Bob不能去指向防御点的点以此类推…
已知终态不知起始态其实与期望dp类似启发我们建反图后从防御点拓扑排序 然后考虑类似拓扑排序的更新流程实际就是sg函数的思想
初始时将防御点放入队列
对二分图上的点每个点计算一个dp值
如果防御点位于左侧则Alice到这个点就视为在只考虑这个防御点时获胜置dp值为1
如果防御点位于右侧则Bob到这个点就视为失败置dp置为0
如果一个点的所有下游反图的上游都是对方的必胜点则这个点是必败点
如果一个点的所有下游反图的上游存在对方的必败点则这个点是必胜点
如果一个点确定了必胜/必败态就将这个点放入队列直至更新完所有点
跑完这一轮后Alice必败Bob必胜的起点需要被排除 此时有一些点可能是没被更新过的即拓扑排序中的环
这些点的特性是
1. 不存在下游是对方的必败点
2. 存在一部分下游点是对方的必胜点
3. 另一部分下游是状态未确定的点
那如果Alice和Bob在这些点上玩的话都只会走向状态未确定的点使Alice永远走不到防御点
所以这些状态未确定的点也需要被过滤排除 枚举完一个防御点就会过滤掉一些点
枚举完所有点后没被过滤掉的点就是Alice的必胜起点若不存在则Bob必胜
其实感觉是很典的拓扑图上sg问题
代码
#includebits/stdc.h
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,ll P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N605;
int T,n,m,u,v,k,c,dp[N],deg[N],d[N];
bool no[N],can[N];
vectorinte[N];
void add(int u,int v){e[v].pb(u);deg[u];
}
bool L(int x){return xn;
}
bool sol(int s){memset(dp,-1,sizeof dp);for(int i0;inm;i)can[i]0,d[i]deg[i];queueintq;q.push(s);dp[s]L(s);//点s表示GG想走到这里YY不想走到这里位于左侧GG赢位于右侧YY输can[s]1;while(!q.empty()){int uq.front();q.pop();for(auto v:e[u]){can[v]1;--d[v];if(~dp[v])continue;if(dp[u]0)dp[v]1;if(dp[u]1 !d[v])dp[v]0;if(~dp[v])q.push(v);}}for(int i0;inm;i){if(!can[i])return 0;if(L(i) dp[i]0)no[i]1;if(!L(i) dp[i]1)no[i]1;if(dp[i]-1)no[i]1;}return 1;
}
bool solve(){for(int i0;inm;i){if(!deg[i])return 0;}memset(no,0,sizeof no);for(int i0;inm;i){if(!sol(i))return 0;}for(int i0;inm;i){if(!no[i])return 1;}return 0;
}
int main(){scanf(%d,T);while(T--){scanf(%d%d,n,m);for(int i0;inm;i){e[i].clear();deg[i]0;}for(int i0;in;i){scanf(%d,k);for(int j1;jk;j){scanf(%d,v);add(i,nv);}}for(int i0;im;i){scanf(%d,k);for(int j1;jk;j){scanf(%d,v);add(ni,v);}}puts(solve()?Yes:No);}return 0;
}
