网络流建模方法（四）互不攻击问题，或者说是共存问题， 这类题目看起来有点像二分图匹配，这类题目我们就是建一个二分图然后跑最大流
还是先说题目洛谷P3353
题目描述
在一个 nn个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入
对于给定的 nn 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击
输入格式
第一行有 2 个正整数n 和 m (1<=n<=200, 0<=m<n2)，分别表示棋盘的大小和障碍数。接下来的 m 行给出障碍的位置。每行 2 个正整数，表示障碍的方格坐标。
输出格式
将计算出的共存骑士数输出
输入
3 2
1 1
3 3
输出
5
---------------------------------------------------------------------------------------------------------------------------------------
通过题意我们很容易发现这是一个最小割问题，为什么这么说呢？对于骑士我们有两种状态，<mark>1.放在棋盘中、2.不放在棋盘中</mark>那么我们先来建一个二分图，对于权值我们赋予1，（这样好计算总共有多少骑士被放于棋盘中），那么我们假设把所有的骑士都连接在一起并且放于棋盘中，那么这样的话骑士肯定会互相攻击，也就违背了题意，那么我们肯定是要断开一些连接，也就是取走一些骑士，那么断掉哪些边呢，肯定是越少越好，诶~~~~~~~这是啥？？？最小割，最小割也就是最大流，那么我们就建图跑最大流好了，<mark>注意一个坑点就是骑士可以走八个方向</mark> 看到这如果你觉得很难理解的话那么你可以去看一下洛谷的P2774方格取数问题，这两种题型是一样的但是方格取数会更简单一些，方格取数问题，看下面的讲解
---------------------------------------------------------------------------------------------------------------------------------------
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<string>
using namespace std;
const int MAXN = 3e6 + 5;
const int INF = 0x3f3f3f3f;
int fx[8]={1,1,-1,-1,2,2,-2,-2},fy[8]={2,-2,2,-2,1,-1,1,-1};
struct Edge
{
int to, w, next;
}edg[MAXN];
int head[MAXN], visit[1000][1000], dep[MAXN];
int cnt = 0;
void init()
{
memset(head, -1, sizeof(head));
cnt = 0;
}
void Add_edge(int u, int v, int w)
{
edg[cnt].to = v;
edg[cnt].w = w;
edg[cnt].next = head[u];
head[u] = cnt++;
edg[cnt].to = u;
edg[cnt].w = 0;
edg[cnt].next = head[v];
head[v] = cnt++;
}
bool BFS(int s, int t)
{
queue<int> q;
while(!q.empty())
{
q.pop();
}
memset(dep, 0, sizeof(dep));
dep[s] = 1;
//flow[s] = INF;
q.push(s);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = head[u]; i != -1; i = edg[i].next)
{
int v = edg[i].to;
if(edg[i].w && dep[v] == 0)
{
dep[v] = dep[u] + 1;
q.push(v);
if(v == t)
return true;
}
}
}
return false;
}
int DFS(int s, int mw, int t)
{
if(s == t)
return mw;
int res = 0;
for(int i = head[s]; i != -1 && res < mw; i = edg[i].next)
{
int v = edg[i].to;
if(edg[i].w && dep[v] == dep[s] + 1)
{
int k = DFS(v, min(mw - res, edg[i].w), t);
if(!k) dep[v] = 0;
edg[i].w -= k;
edg[i^1].w += k;
res += k;
}
}
return res;
}
int Dinic(int s, int t)
{
int tot = 0;
while(BFS(s, t))
{
while(int d = DFS(s, INF, t))
{
tot += d;
}
}
return tot;
}
int main()
{
memset(visit, 0, sizeof visit);
int n, m;
scanf("%d %d", &n, &m);
int s = 0, t = n * n + 1;
init();
for(int i = 1; i <= m; ++i)
{
int x, y;
scanf("%d %d", &x, &y);
visit[x][y] = 1;
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
if((i + j) & 1)
{
if(!visit[i][j])
Add_edge(s, (i - 1) * n + j, 1);
}
else
{
if(!visit[i][j])
Add_edge((i - 1) * n + j, t, 1);
}
}
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
if(((i + j) & 1) == 0)
continue;
for(int k = 0; k < 8; k++)
{
int x = i + fx[k];
int y = j + fy[k];
if(x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y])
{
Add_edge((i - 1) * n + j, (x - 1) * n + y, INF);
}
}
}
}
int ans = Dinic(s, t);
//cout << ans << endl;
printf("%d\n", (n * n) - m - ans);
}
题目描述
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
输入格式
第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。
输出格式
程序运行结束时，将取数的最大总和输出
输入
3 3
1 2 3
3 2 3
2 3 1
输出
11
说明/提示
m,n<=100
---------------------------------------------------------------------------------------------------------------------------------------
对于方格取数问题，其实本质上是和骑士共存问题一样的，我们同样是奇偶建二分图跑最小割，直接上代码
---------------------------------------------------------------------------------------------------------------------------------------
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<string>
using namespace std;
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int fx[4]={0,0,1,-1};
const int fy[4]={1,-1,0,0};
struct Edge
{
int to, w, next;
}edg[MAXN];
int head[MAXN], flow[MAXN], dep[MAXN];
int cnt = 0;
void init()
{
memset(head, -1, sizeof(head));
cnt = 0;
}
void Add_edge(int u, int v, int w)
{
edg[cnt].to = v;
edg[cnt].w = w;
edg[cnt].next = head[u];
head[u] = cnt++;
edg[cnt].to = u;
edg[cnt].w = 0;
edg[cnt].next = head[v];
head[v] = cnt++;
}
bool BFS(int s, int t)
{
queue<int> q;
while(!q.empty())
{
q.pop();
}
memset(dep, 0, sizeof(dep));
dep[s] = 1;
flow[s] = INF;
q.push(s);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = head[u]; i != -1; i = edg[i].next)
{
int v = edg[i].to;
if(edg[i].w && dep[v] == 0)
{
dep[v] = dep[u] + 1;
q.push(v);
if(v == t)
return true;
}
}
}
return false;
}
int DFS(int s, int mw, int t)
{
if(s == t)
return mw;
int res = 0;
for(int i = head[s]; i != -1 && res < mw; i = edg[i].next)
{
int v = edg[i].to;
if(edg[i].w && dep[v] == dep[s] + 1)
{
int k = DFS(v, min(mw - res, edg[i].w), t);
if(!k) dep[v] = 0;
edg[i].w -= k;
edg[i^1].w += k;
res += k;
}
}
return res;
}
int main()
{
int n, m, x, sum = 0;
scanf("%d %d", &n, &m);
init();
int s = 0, t = n * m + 1;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
scanf("%d", &x);
sum += x;
if((i +j) % 2 == 1)
{
Add_edge(s, (i - 1) * m + j, x);
}
else
Add_edge((i - 1) * m + j, t, x);
}
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if((i + j) % 2 == 1)
{
for(int k = 0; k < 4; ++k)
{
int x = i + fx[k];
int y = j + fy[k];
if(x > n || x <= 0 || y > m || y <= 0)
continue;
Add_edge((i - 1) * m + j, (x - 1) * m + y, INF);
}
}
}
}
while(BFS(s, t))
sum -= DFS(s, INF, t);
printf("%d\n", sum);
}
京公网安备 11010502036488号