【codechef】【May Challenge 2019 Division 2】【Ada Pawns】题解

[题目链接](https://www.codechef.com/MAY19B/problems/ADAPWN) ### 题目描述 给定一个 $n \times n$ 的国际象棋棋盘，上面有一些棋子 在 $(x,y)$ 的棋子可以吃掉 $(x-1,y-1)$ 的棋子或者 $(x-1,y+1)$ 的棋子，每一步必须吃子 如果无子可吃，则结束游戏 构造一种方案，使得结束游戏的时间最小（也就是尽量少的吃子） ### 题解 相当于一个棋子可以移除当且仅当它左上方或者右上方有至少一个棋子 考虑最小割 把棋盘按照行的奇偶性黑白染色 代码如下： ``` cpp for(int i = 1 ; i <= n ; ++ i) { for(int j = 1 ; j <= n ; ++ j) { if(str[i][j] == 'O') { if(str[i - 1][j - 1] == 'O' || str[i - 1][j + 1] == 'O') { if(i & 1) { add(s, ids[i][j], 1); } else { add(ids[i][j], t, 1); } } else { if(i & 1) { add(s, ids[i][j], inf); } else { add(ids[i][j], t, inf); } } for(int k = 0 ; k < 2 ; ++ k) { int x = i + mv[k][0], y = j + mv[k][1]; if(1 <= x && x <= n && 1 <= y && y <= n && str[x][y] == 'O') { if(i % 2 == 1) { add(ids[i][j], ids[x][y], inf); } else { add(ids[x][y], ids[i][j], inf); } } } } } } ``` 考虑输出方案，那么就是求 $S$ 集 从 $S$ 开始 $bfs$，沿着跑完网络流的图上的正边权走，能到达的点集就是 $S$ 集，剩下的是 $T$ 集，连接这两个集合的边是割边 智障选手欢乐多系列： ``` cpp queue<int> q; q.push(s); while(q.size()) { int u = q.front(); q.pop(); vis[u] = 1; for(int i = head[u] ; i ; i = rest[i]) { int v = to[i]; if(w[i] && !vis[v]) { q.push(v); } } } ``` 实际上应该在入队的时候就打上 $vis$ 标记……