B. MADMAX(记搜+博弈)

$感觉还是很巧妙啊$

$设dp[x][y][k]表示先手在x,后手在y,上一次边权是k的胜负情况$

$那么x先手,所以把x能走的所有路走一遍$

$只要存在一条路赢了就赢了,否则输了$

$这个过程用记忆化搜索很方便实现$

#include <bits/stdc++.h> using namespace std; #define f first #define s second #define pb push_back const int maxn=209; int dp[maxn][maxn][maxn],n,m; typedef pair<int,int>p; vector<p>vec[maxn]; bool DP(int x,int y,int k)//x先手,y后手,当前边权为k { if( dp[x][y][k]!=-1 ) return dp[x][y][k]; for(int i=0;i<vec[x].size();i++) { int v=vec[x][i].f,cost=vec[x][i].s; if(cost>=k&&DP(y,v,cost)==0)//如果y必输 return dp[x][y][k]=1;//x先手必胜 } return dp[x][y][k]=0;//没有x可以赢得路,必须输掉了 } int main() { cin >> n >> m; for(int i=1;i<=m;i++) { int l,r;char w; cin>>l>>r>>w; vec[l].pb(p(r,w)); } memset(dp,-1,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) DP(i,j,0); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(dp[i][j][0]) cout<<'A'; else cout<<"B"; if(j==n) cout<<endl; } }