首页 > 其他 > 详细

【洛谷】2172: [国家集训队]部落战争【二分图/网络流】【最小路径覆盖】

时间:2018-10-16 17:12:16      阅读:176      评论:0      收藏:0      [点我收藏+]

P2172 [国家集训队]部落战争

题目描述

lanzerb的部落在A国的上部,他们不满天寒地冻的环境,于是准备向A国的下部征战来获得更大的领土。

A国是一个M*N的矩阵,其中某些地方是城镇,某些地方是高山深涧无人居住。lanzerb把自己的部落分成若干支军队,他们约定:

  1. 每支军队可以从任意一个城镇出发,并只能从上往向下征战,不能回头。途中只能经过城镇,不能经过高山深涧。

  2. 如果某个城镇被某支军队到过,则其他军队不能再去那个城镇了。

  3. 每支军队都可以在任意一个城镇停止征战。

  4. 所有军队都很奇怪,他们走的方法有点像国际象棋中的马。不过马每次只能走1*2的路线,而他们只能走R*C的路线。

lanzerb的野心使得他的目标是统一全国,但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇,请你帮lanzerb算算至少要多少支军队才能完成统一全国的大业。

输入输出格式

输入格式:

 

第一行包含4个整数M、N、R、C,意义见问题描述。接下来M行每行一个长度为N的字符串。如果某个字符是‘.‘,表示这个地方是城镇;如果这个字符时‘x‘,表示这个地方是高山深涧。

 

输出格式:

 

输出一个整数,表示最少的军队个数。

 

输入输出样例

输入样例#1: 复制
3 3 1 2
...
.x.
...
输出样例#1: 复制
4
输入样例#2: 复制
5 4 1 1
....
..x.
...x
....
x...
样例输出
输出样例#2: 复制
5

说明

100%的数据中,1<=M,N<=50,1<=R,C<=10。


Solution

比较轻松地可以想到最小路径覆盖问题,用最少的路径,经过所有点。

二分图是经典方法,每个点拆点,两点间有连边就在二分图上连边,最小路径就等于总点数-最大匹配。可以理解为,每一个匹配,就省去了一条路径(以入点为起点的路径可以由出点直接到达),所以最大匹配省去的路径是最多的。

最大匹配也可以用网络流实现。

注意空间....

Code

#include<bits/stdc++.h>
using namespace std;

int G[105][105], n, m, r, c;
int zl[2][2] = {{1, 1}, {1, -1}};

struct Node {
    int u, v, nex;
    Node(int u = 0, int v = 0, int nex = 0) :
        u(u), v(v), nex(nex) { }
} Edge[1000005];

int h[10005], stot;
void add(int u, int v) {
    Edge[++stot] = Node(u, v, h[u]);
    h[u] = stot;
}

bool check(int x, int y) {
    if(x < 1 || y < 1 || x > m || y > n || !G[x][y])    return 0;
    return 1;
}

int las[10005], to[10005], vis[10005];
bool dfs(int u) {
    for(int i = h[u]; i; i = Edge[i].nex) {
        int v = Edge[i].v;
        if(!vis[v]) {
            vis[v] = 1;
            if(!las[v] || dfs(las[v])) {
                to[u] = v; las[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int id[105][105], ans, tot;
char s[505][505];
int main() {
    scanf("%d%d%d%d\n", &m, &n, &r, &c);
    for(int i = 1; i <= m; i ++)    scanf("%s", s[i] + 1);
    for(int i = 1; i <= m; i ++) {
        for(int j = 1; j <= n; j ++) {
            id[i][j] = (i - 1) * n + j;
            if(s[i][j] == .)    G[i][j] = 1, tot ++;
            else            G[i][j] = 0;
        }
    }
    for(int i = 1; i <= m; i ++)
        for(int j = 1; j <= n; j ++) {
            if(!G[i][j])    continue;
            int x, y;
            for(int k = 0; k < 2; k ++) {
                x = i + zl[k][0] * r, y = j + zl[k][1] * c;
                if(!check(x, y))    continue;
                add(id[i][j], id[x][y] + n * m);
            }
            if(r != c) {
                for(int k = 0; k < 2; k ++) {
                    x = i + zl[k][0] * c, y = j + zl[k][1] * r;
                    if(!check(x, y))    continue;
                    add(id[i][j], id[x][y] + n * m);
                }
            }
        }
    for(int i = 1; i <= m; i ++) {
        for(int j = 1; j <= n; j ++)
            if(!to[id[i][j]] && G[i][j]) {
                memset(vis, 0, sizeof(vis));
                ans += dfs(id[i][j]);
            }
    }
    printf("%d", tot - ans);
    return 0;
}

【洛谷】2172: [国家集训队]部落战争【二分图/网络流】【最小路径覆盖】

原文:https://www.cnblogs.com/wans-caesar-02111007/p/9798727.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!