P2172 [国家集训队]部落战争 二分图最小不相交路径覆盖

时间:2021-07-16 13:19:17

二分图最小不相交路径覆盖

#include<bits/stdc++.h>
using namespace std;
const int MAXN = ;
const int MAXM = ;
const int INF = ;
int Head[MAXN], cur[MAXN], lev[MAXN], to[MAXM << ], nxt[MAXM << ], f[MAXM << ], ed = , S, T;
inline void addedge(int u, int v, int cap)
{
to[++ed] = v;
nxt[ed] = Head[u];
Head[u] = ed;
f[ed] = cap;
to[++ed] = u;
nxt[ed] = Head[v];
Head[v] = ed;
f[ed] = ;
return;
}
inline bool BFS()
{
int u;
memset(lev, -, sizeof(lev));
queue<int>q;
lev[S] = ;
q.push(S);
while (q.size()) {
u = q.front();
q.pop();
for (int i = Head[u]; i; i = nxt[i])
if (f[i] && lev[to[i]] == -) {
lev[to[i]] = lev[u] + ;
q.push(to[i]);
/*
if (to[i] == T)
{
return 1;
}
magic one way optimize
*/
}
}
memcpy(cur, Head, sizeof Head);
return lev[T] != -;
}
inline int DFS(int u, int maxf)
{
if (u == T || !maxf) {
return maxf;
}
int cnt = ;
for (int &i = cur[u], tem; i; i = nxt[i])
if (f[i] && lev[to[i]] == lev[u] + ) {
tem = DFS(to[i], min(maxf, f[i]));
maxf -= tem;
f[i] -= tem;
f[i ^ ] += tem;
cnt += tem;
if (!maxf) {
break;
}
}
if (!cnt) {
lev[u] = -;
}
return cnt;
}
int Dinic()
{
int ans = ;
while (BFS()) {
ans += DFS(S, );
}
return ans;
}
void init(int SS, int TT)
{
memset(Head, , sizeof(Head));
ed = ;
S = SS;
T = TT;
return;
}
char ff[][];
int dir[][];
int aim[][];
int cnt = ;
int main()
{
int n, m;
int r, c;
int u, v;
scanf("%d %d %d %d", &n, &m, &r, &c);
dir[][] = dir[][] = r;
dir[][] = dir[][] = c;
dir[][] = c, dir[][] = r;
dir[][] = -r, dir[][] = -c;
if(r==c)
{
dir[][]=dir[][]=dir[][]=dir[][]=;
}
for (int i = ; i <= n; i++) {
scanf("%s", ff[i]+);
}
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
if (ff[i][j] == '.') {
aim[i][j] = ++cnt;
}
}
}
S = , T = * cnt + ;
for (int i = ; i <= cnt; i++) {
addedge(S, i, );
addedge(cnt + i, T, );
}
for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++) {
if (ff[i][j] == '.') {
for (int k = ; k <= ; k++) {
int dx = i + dir[k][];
int dy = j + dir[k][];
if (dx >= && dx <= n && dy >= && dy <= m) {
if (ff[dx][dy] == '.') {
u = aim[i][j], v = aim[dx][dy] + cnt;
addedge(u, v, );
//cout<<i<<" "<<j<<" "<<dx<<" "<<dy<<endl;
}
}
}
}
}
cout << cnt - Dinic() << endl;
return ;
}

P2172 [国家集训队]部落战争 二分图最小不相交路径覆盖的更多相关文章

  1. P2172 &lbrack;国家集训队&rsqb;部落战争(最小路径覆盖)

    P2172 [国家集训队]部落战争 每个点仅走一次:最小路径覆盖 套路地拆点,具体看代码中的$draw()$ 流量每增加1,意味着一支军队可以多走一格,代价减少1 最后答案即为总点数$-dinic() ...

  2. 国家集训队 部落战争 网络流最小路径覆盖 洛谷P2172

    洛谷AC传送门! step1: 题目大意 有一张M x N的网格图,有一些点为“ * ”可以走,有一些点为“ x ”不能走,每走一步你都可以移动R * C 个格子(参考象棋中马的走法),且不能回头,已 ...

  3. 洛谷P2172 &lbrack;国家集训队&rsqb;部落战争 题解

    题目链接:https://www.luogu.org/problemnew/show/P2172 分析: 不要被[国家集训队]的标签吓到,其实这题不是很难. 本题可以对比P4304 [TJOI2013 ...

  4. 【洛谷】4304:&lbrack;TJOI2013&rsqb;攻击装置【最大点独立集】【二分图】2172: &lbrack;国家集训队&rsqb;部落战争【二分图&sol;网络流】【最小路径覆盖】

    P4304 [TJOI2013]攻击装置 题目描述 给定一个01矩阵,其中你可以在0的位置放置攻击装置. 每一个攻击装置(x,y)都可以按照“日”字攻击其周围的8个位置(x-1,y-2),(x-2,y ...

  5. Air Raid POJ - 1422 【有向无环图(DAG)的最小路径覆盖【最小不相交路径覆盖】 模板题】

    Consider a town where all the streets are one-way and each street leads from one intersection to ano ...

  6. &lbrack;luoguP2765&rsqb; 魔术球问题(最大流—最小不相交路径覆盖)

    传送门 枚举球的个数 num 如果 i < j && (i + j) 是完全平方数,那么 i -> j' 连一条边 再加一个超级源点 s,s -> i 再加一个超级汇 ...

  7. POJ Air Raid 【DAG的最小不相交路径覆盖】

    传送门:http://poj.org/problem?id=1422 Air Raid Time Limit: 1000MS   Memory Limit: 10000K Total Submissi ...

  8. &lbrack;国家集训队&rsqb;部落战争 最大流 BZOJ2150

    题目描述 lanzerb的部落在A国的上部,他们不满天寒地冻的环境,于是准备向A国的下部征战来获得更大的领土. A国是一个M*N的矩阵,其中某些地方是城镇,某些地方是高山深涧无人居住.lanzerb把 ...

  9. POJ1422Air Raid(二分图,最小不相交路径覆盖)

    Air Raid Consider a town where all the streets are one-way and each street leads from one intersecti ...

随机推荐

  1. s3c2440 移值u-boot-2016&period;03 第5篇 支持dm9000 识别

    1, 通过查看 /drivers/net/Makefile 发现想要编译上,需要添加宏 /include/configs/smdk2440.h 中添加 #define CONFIG_DRIVER_DM ...

  2. openstack虚拟机迁移的操作记录

    需求说明:计算节点linux-node1.openstack:192.168.1.8  计算节点linux-node2.openstack:192.168.1.17 这两个计算节点在同一个控制节点下( ...

  3. int和long int的区别

    16位系统:long是4字节,int是2字节32位系统:long是4字节,int是4字节64位系统:long是8字节,int是4字节 long long 占8个字节

  4. jenkins:应用篇(Gatling plugin的使用)

    Jenkins的功能强大,在于它的插件式框架,能扩展功能,自动化当中,很容易想到的是对提交的新代码做测试,这里gatling主要是负责压力测试,也就是所谓的性能.关于gatling,可以参考我前面的博 ...

  5. 利用Openvswitch实现不同物理机中的Docker容器互连

    1. 测试环境 75机(10.11.150.75):Red Hat Enterprise Linux Server 7.0,无外网访问权限,已安装Docker Server 74机(10.11.150 ...

  6. Set up your first C&num; test with NUnit or resharper

    此链接为一种方式,用Nunit单元测试驱动测试代码 http://relevantcodes.com/using-nunit-to-execute-selenium-webdriver-tests/ ...

  7. Log4net 可直接使用的配置

    config配置 <xml version="1.0"> <configuration> <configSections> <!--配置一 ...

  8. spring 上传文件文件的一个例子,

    /** * 类名称:UploadTest 类描述:创建人:zhang 创建时间:2015年3月13日 下午4:20:57 修改人:zhang * 修改时间:2015年3月13日 下午4:20:57 修 ...

  9. JSP报错Syntax error&comma; insert &quot&semi;&semi;&quot&semi; to complete Statement

    org.apache.jasper.JasperException: Unable to compile class for JSP: An error occurred at line: 7 in ...

  10. Spring Security ——AuthenticationProvider

    AuthenticationProvider 目录 1.1     用户信息从数据库获取 1.1.1    使用jdbc-user-service获取 1.1.2    直接使用JdbcDaoImpl ...