网格图是一个天然二分图, 可以按 横纵坐标之和 的奇偶性将相邻两格分属于左部和右部。
记’?’ 或 ‘2’ 的格子为待匹配点, 记横纵坐标之和为奇数的为奇待匹配点, 即(i + j)为odd
将匹配点向相邻匹配点连边,建 S 和 T 超级源汇, 将 S 与奇待匹配点连边, 偶待匹配点与T连边
容量皆为1, 跑一边最大流,最后检查与S, T 相连的 ‘2’ 边是否都为零即可。
可惜的是,这种思路只能过赛时数据,被after-contest hack掉了, 这里提供一组数据
Input
4 4
11?1
?222
1211
1?11
Output
Yes
可以看出, 最大流有多种情况, 2与2 的方格不一定能连边
所以只能跑一遍有源汇上下界可行流了。
#include <bits/stdc++.h>
#define for_(i,a,b) for (ll i = (a); i < (b); i++)
#define rep_(i,a,b) for (ll i = (a); i <= (b); i++)
#define fi first
#define se second
#define sz(a) a.size()
using namespace std;
const int maxn = 1e6 + 10, mod = 1e9 + 7;// mod = 1949777;
const double EPS = 1e-3;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
int n, m;
char c[505][505];
int inf = 1 << 29;
int id[505][505];
int dx[5] = {0, 0, 1, -1};
int dy[5] = {1, -1, 0, 0};
int d[maxn];
int tot = 1, maxflow;
int nxt[maxn], head[maxn], v[maxn], e[maxn], tag[maxn];
int now[maxn];// 当前弧优化
int Vin[maxn], Vout[maxn];
void add(int x, int y, int c) {
v[++tot] = y, e[tot] = c, nxt[tot] = head[x]; head[x] = tot;
v[++tot] = x, e[tot] = 0, nxt[tot] = head[y], head[y] = tot;
}
int s, t;
bool bfs(){
memset(d, 0, sizeof(d));
queue<int> q;
q.push(s);
d[s] = 1; now[s] = head[s];
while(q.size()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = nxt[i]) {
if (e[i] && !d[v[i]]) {
d[v[i]] = d[x] + 1;
now[v[i]] = head[v[i]];
q.push(v[i]);
if (v[i] == t) return 1;
}
}
}
return 0;
}
int dinic(int x, int flow){
if (x == t) return flow;
int res = flow, k;
for (int i = now[x]; i && res; i = nxt[i]) {
now[x] = i;
if (e[i] && d[v[i]] == d[x] + 1) {
k = dinic(v[i], min(res, e[i]));
if (!k) d[v[i]] = 0;
e[i] -= k;
e[i^1] += k;
res -= k;
}
}
return flow - res;
}
int cnt = 0;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> c[i][j];
id[i][j] = ++cnt; // 标号 预处理比较方便...
}
}
s = 0, t = n * m + 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (c[i][j] == '1') continue;
if ((i + j) & 1) { // 奇带匹配点
if (c[i][j] == '2') {
add(s, id[i][j], 0); // 连一条upper减去lower的边 此处上界为1, 下界为1 , 1 - 1 = 0
// 也可以不连, 此处写出是为了清楚
Vin[id[i][j]]++; // 处于维护流量平衡, 需要记录每个点的流入量&流出量
Vout[s]++;
} else add(s, id[i][j], 1);
for (int k = 0; k < 4; k++) {
int nx = i + dx[k], ny = j + dy[k];
if (nx >= 1 && ny >= 1 && nx <= n && ny <= m) {
add(id[i][j], id[nx][ny], 1); //带匹配点连边
}
}
} else {
if (c[i][j] == '2') { //同上
Vin[t]++;
Vout[id[i][j]]++;
add(id[i][j], t, 0);
} else add(id[i][j], t, 1);
}
}
}
add(t, s, 1e9); // 原图的汇向源连一条inf边,以下皆是上下界可行流的常规操作。
s = n * m + 2, t = n * m + 3; // 新建源汇
for (int i = 0; i <= n * m + 1; i++) {
if (Vin[i] > Vout[i]) {
add(s, i, Vin[i] - Vout[i]);
} else if (Vin[i] < Vout[i]){
add(i, t, Vout[i] - Vin[i]);
}
}
int flow, maxflow = 0;
// 在差网络上跑最大流
while(bfs()) {
while(flow = dinic(s, inf)) maxflow += flow;
}
int ok = 1;
for (int i = head[s]; i; i = nxt[i]) {
if (e[i]) ok = 0; //判断有无解
}
if (ok) cout << "Yes" << endl;
else cout << "No" <<endl;
return 0;
}
原先的最大流思路真的不行吗?
如果我们跳出网络流是个天然二分图这个思路, 重新建图,另辟蹊径,即是柳暗花明。
我们知道,原先的想法只是卡在达到最大匹配数但是不是所有的2都被匹配。我们是不是可以交换一些’?'与’2’的匹配, 转而变成’2’与’2‘ 的匹配,我看到洛谷上有大神已经怎么写的了,他是不断寻找增广路, 使得每一个’2‘都尽可能被匹配,在此%%%。
也可以重新建图,求出最大匹配, 然后看匹配数是否等于2的个数即可
#include <bits/stdc++.h>
#define for_(i,a,b) for (ll i = (a); i < (b); i++)
#define rep_(i,a,b) for (ll i = (a); i <= (b); i++)
#define fi first
#define se second
#define sz(a) a.size()
#define int long long
#define pb push_back
#define CE cout << endl;
#define CO cout << "OK" << endl;
using namespace std;
const int maxn = 2e6 + 10, mod = 1e9 + 7;// mod = 1949777;
const double EPS = 1e-3;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
int n, m;
char c[505][505];
int inf = 1 << 29;
int id[505][505];
int dx[5] = {0, 0, 1, -1};
int dy[5] = {1, -1, 0, 0};
int d[maxn];
int tot = 1, maxflow;
int nxt[maxn], head[maxn], v[maxn], e[maxn], tag[maxn];
int now[maxn];// 当前弧优化
int Vin[maxn], Vout[maxn];
void add(int x, int y, int c) {
v[++tot] = y, e[tot] = c, nxt[tot] = head[x]; head[x] = tot;
v[++tot] = x, e[tot] = 0, nxt[tot] = head[y], head[y] = tot;
}
int s, t;
bool bfs(){
memset(d, 0, sizeof(d));
queue<int> q;
q.push(s);
d[s] = 1; now[s] = head[s];
while(q.size()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = nxt[i]) {
if (e[i] && !d[v[i]]) {
d[v[i]] = d[x] + 1;
now[v[i]] = head[v[i]];
q.push(v[i]);
if (v[i] == t) return 1;
}
}
}
return 0;
}
int dinic(int x, int flow){
if (x == t) return flow;
int res = flow, k;
for (int i = now[x]; i && res; i = nxt[i]) {
now[x] = i;
if (e[i] && d[v[i]] == d[x] + 1) {
k = dinic(v[i], min(res, e[i]));
if (!k) d[v[i]] = 0;
e[i] -= k;
e[i^1] += k;
res -= k;
}
}
return flow - res;
}
int cnt = 0;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>> n >> m;
int K = 0;
for (int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> c[i][j];
if (c[i][j] == '2') K++;
id[i][j] = ++cnt;
}
}
s = 0, t = 3 * n * m + 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (c[i][j] == '1') continue;
if (c[i][j] == '2') {
add(s, id[i][j], 1);
for (int k = 0; k < 4; k++) {
int nx = i + dx[k], ny = j + dy[k];
if (nx >= 1 && ny >= 1 && nx <= n && ny <= m) {
if (c[nx][ny] != '1') add(id[i][j], id[nx][ny] + n * m, 1);
}
}
}
add(id[i][j] + n * m, t, 1);
}
}
int flow, maxflow = 0;
while(bfs()) {
while(flow = dinic(s, inf)) maxflow += flow;
}
if (maxflow == K) cout << "Yes" << endl;
else cout << "No" <<endl;
return 0;
}