首页 > 代码库 > Gym 101246D Fire in the Country（dfs求SG函数）
Gym 101246D Fire in the Country（dfs求SG函数）
http://codeforces.com/gym/101246/problem/D
题意：
给定一个无向有环图，大火从1点开始，每个时间点与它相邻的点也将会着火，现在有两个人轮流操作机器人，机器人从1点出发，每个人每次选择一个点走，谁最后被火烧了谁就输了。
思路：
博弈题。
我们先预处理求出每个点着火的时间点，然后根据时间点重建新图，也就是重新建一个有向无环图，原来图中相连的并且时间点相差1的相连，由时间低的连向时间高的。
接下来我们在新图上求每个点的SG值，SG值为0的点就是叶子结点，这样父亲结点的SG值就可以通过子节点的SG值求出，也就是求mex。
最后我们可以求出根结点的SG值，也就是SG【1】的值。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<cstdio> 12 #include<set> 13 using namespace std; 14 typedef long long ll; 15 typedef pair<int,int> pll; 16 const int INF = 0x3f3f3f3f; 17 const int maxn=1000+5; 18 19 int n, m; 20 21 int t[maxn]; 22 int SG[maxn]; 23 int vis[maxn]; 24 25 vector<int> G[maxn]; 26 vector<int> new_G[maxn]; 27 28 //求时间点 29 void bfs() 30 { 31 memset(t, -1, sizeof(t)); 32 queue<int> Q; 33 Q.push(1); 34 t[1]=1; 35 while(!Q.empty()) 36 { 37 int u = Q.front(); Q.pop(); 38 for(int i = 0; i < G[u].size(); i++) 39 { 40 int v = G[u][i]; 41 if(t[v] != -1) continue; 42 t[v] = t[u] + 1; 43 Q.push(v); 44 } 45 } 46 } 47 48 //建新图 49 void re_build() 50 { 51 for(int i = 1; i <= n; i++) 52 { 53 for(int j = 0; j < G[i].size(); j++) 54 { 55 int v = G[i][j]; 56 if(t[v] == t[i] + 1) 57 new_G[i].push_back(v); 58 } 59 } 60 } 61 62 //求SG 63 void dfs(int u) 64 { 65 if(new_G[u].size() == 0) 66 { 67 SG[u] = 0; 68 return; 69 } 70 for(int i = 0; i < new_G[u].size(); i++) 71 { 72 int v = new_G[u][i]; 73 dfs(v); 74 } 75 76 //求mex，也就是父亲结点的SG值 77 for(int i = 0; ;i++) 78 { 79 bool flag = false; 80 for(int j = 0; j < new_G[u].size(); j++) 81 { 82 if(SG[new_G[u][j]] == i) 83 { 84 flag = true; 85 break; 86 } 87 } 88 if(flag == false) 89 { 90 SG[u] = i; 91 break; 92 } 93 } 94 } 95 96 97 int main() 98 { 99 freopen("input.txt","r",stdin);100 freopen("output.txt","w",stdout);101 // freopen("in.txt","r",stdin);102 while(~scanf("%d%d",&n, &m))103 {104 for(int i = 1; i <= n; i++) {G[i].clear(); new_G[i].clear();}105 106 for(int i = 0; i < m; i++)107 {108 int u, v;109 scanf("%d%d",&u, &v);110 G[u].push_back(v);111 G[v].push_back(u);112 }113 114 bfs();115 re_build();116 dfs(1);117 if(SG[1] == 0) puts("Nikolay");118 else puts("Vladimir");119 }120 return 0;121 }
Gym 101246D Fire in the Country（dfs求SG函数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。