题 目 传 送 门 在 这
题目大意
题目都很简短了就不说了......(懒得打)
解题思路
我们把行和列都看作节点, 对于每个可以放位置, 连一条行到列的边.
我们发现这是一个二分图.
因为车不能互相攻击, 对于第一行, 只能放一个车, 对于每一列也是如此, 所以每个节点只有一条连边.
那么就符合二分图匹配中每两条边没有公共节点.
本题就变成求二分图最大匹配的题目.
代码如下:
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #define rep(x, l, r) for(int x = l; x <= r; x++)
- #define repd(x, r, l) for(int x = r; x>= l; x--)
- #define clr(x, y) memset(x, y, sizeof(x))
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define mp make_pair
- #define MAXN 105
- #define MAXM 40005
- #define fi first
- #define se second
- #define SZ(x) ((int)x.size())
- using namespace std;
- typedef long long LL;
- typedef vector<int> vi;
- typedef pair<int, int> pii;
- const int INF = 0x3f3f3f3f;
- const int p = 10000007;
- int lowbit(int x){ return x & -x; }
- int fast_power(int a, int b){ int x; for(x = 1; b; b>>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p; } return x; }
- const int dic[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
- int n, m, cnt;
- int head[MAXN * MAXN], nxt[MAXM], to[MAXM];
- int match[MAXN * MAXN];
- bool g[MAXN][MAXN], vis[MAXN * MAXN];
- void init(){
- cnt = 0;
- clr(head, -1);
- clr(match, 0);
- }
- int id(int x, int y){
- return (x - 1) * n + y;
- }
- void add(int u, int v){
- nxt[cnt] = head[u];
- head[u] = cnt;
- to[cnt] = v;
- cnt++;
- }
- bool dfs(int u){
- for(int e = head[u]; e != -1; e = nxt[e]){
- int v = to[e];
- if(vis[v]) continue;
- vis[v] = 1;
- if(!match[v] || dfs(match[v])){
- match[v] = u;
- return 1;
- }
- }
- return 0;
- }
- int main(){
- init();
- scanf("%d%d", &n, &m);
- rep(i, 1, m){
- int x, y;
- scanf("%d%d", &x, &y);
- g[x][y] = 1;
- }
- rep(i, 1, n)
- rep(j, 1, n)
- if(!g[i][j])
- rep(k, 0, 3){
- int x = i + dic[k][0], y = j + dic[k][1];
- if(x> 0 && y> 0 && x <= n && y <= n && !g[x][y] && (x + y) % 2){
- add(id(i, j), id(x, y));
- }
- }
- int ans = 0;
- rep(i, 1, id(n, n)){
- clr(vis, 0);
- if(dfs(i)) ans++;
- }
- printf("%d\n", ans);
- return 0;
- }
最后问一下, 为什么 Mac 自带输入法打不出 "車".
来源: http://www.bubuko.com/infodetail-2940997.html