当前位置: 代码迷 >> 综合 >> BZOJ1412 [ZJOI2009]狼和羊的故事 【最小割】
  详细解决方案

BZOJ1412 [ZJOI2009]狼和羊的故事 【最小割】

热度:63   发布时间:2023-12-25 04:57:54.0

1412: [ZJOI2009]狼和羊的故事

Time Limit: 10 Sec   Memory Limit: 162 MB
Submit: 3454   Solved: 1733
[Submit][Status][Discuss]

Description

“狼爱上羊啊爱的疯狂,谁让他们真爱了一场;狼爱上羊啊并不荒唐,他们说有爱就有方向......” Orez听到这首歌,心想:狼和羊如此和谐,为什么不尝试羊狼合养呢?说干就干! Orez的羊狼圈可以看作一个n*m个矩阵格子,这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼,它们总是对羊垂涎三尺,那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆,还是要将羊狼分开来养。 通过仔细观察,Orez发现狼和羊都有属于自己领地,若狼和羊们不能呆在自己的领地,那它们就会变得非常暴躁,不利于他们的成长。 Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地,再就是篱笆必须修筑完整,也就是说必须修建在单位格子的边界上并且不能只修建一部分。

Input

文件的第一行包含两个整数n和m。接下来n行每行m个整数,1表示该格子属于狼的领地,2表示属于羊的领地,0表示该格子不是任何一只动物的领地。

Output

文件中仅包含一个整数ans,代表篱笆的最短长度。

Sample Input

2 2
2 2
1 1

Sample Output

2

数据范围
10%的数据 n,m≤3
30%的数据 n,m≤20
100%的数据 n,m≤100

为何狼羊与最小割总是联系到一块?

因为它们总是要被分割开【分割开,割开,开】

把矩阵每个单元看做一个点,向四周单元引一条容量为1的边【每建一个围栏代价为1】

如果属于羊,由S引一条容量为INF的边

如果属于狼,向T引一条容量为INF的边

这样最小割的边一定不是S和T相关的,而狼属于T,羊属于S,最小割算法就可以用最小的代价把它们分割开

其实想到最小割就很容易想到了

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 10005,maxm = 100005,maxv = 105,INF = 1000000000;
inline int RD(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}return out * flag;
}
int n,m,S,T,d[maxn],X[4] = {0,0,-1,1},Y[4] = {1,-1,0,0},q[maxn],cur[maxn];
bool vis[maxn];
int head[maxn],nedge = 0;
struct EDGE{int to,f,next;}edge[maxm];
inline void build(int u,int v,int w){edge[nedge] = (EDGE){v,w,head[u]}; head[u] = nedge++;edge[nedge] = (EDGE){u,0,head[v]}; head[v] = nedge++;
}
bool bfs(){for (int i = 0; i <= T; i++) vis[i] = false;int u,h = 0,t = 0,to;d[S] = 0; vis[S] = true; q[++t] = S;while (h < t){u = q[++h];Redge(u) if (edge[k].f && !vis[to = edge[k].to]){d[to] = d[u] + 1; vis[to] = true; q[++t] = to;}}return vis[T];
}
int dfs(int u,int minf){if (u == T || !minf) return minf;int flow = 0,f,to;if (cur[u] == -2) cur[u] = head[u];for (int& k = cur[u]; k != -1; k = edge[k].next)if (d[to = edge[k].to] == d[u] + 1 && (f = dfs(to,min(minf,edge[k].f)))){edge[k].f -= f;edge[k ^ 1].f += f;flow += f;minf -= f;if (!minf) break;}return flow;
}
int maxflow(){int flow = 0;while (bfs()){fill(cur,cur + maxn,-2);flow += dfs(S,INF);}return flow;
}
inline int id(int x,int y){return m * (x - 1) + y;}
int main(){memset(head,-1,sizeof(head));n = RD(); m = RD(); S = 0; T = n * m + 1; int u,x,y;REP(i,n) REP(j,m){u = id(i,j);for (int k = 0; k < 4; k++){x = i + X[k]; y = j + Y[k];if (x && y && x <= n && y <= m) build(u,id(x,y),1);}x = RD();if (x == 1) build(S,u,INF);else if (x == 2) build(u,T,INF);}cout<<maxflow()<<endl;return 0;
}