最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

今日观点!abc285G

来源：博客园

ABC 285 G - Tatami

Solution 网络流

网格图是一个天然二分图， 可以按 横纵坐标之和 的奇偶性将相邻两格分属于左部和右部。

记"?" 或 ‘2’ 的格子为待匹配点， 记横纵坐标之和为奇数的为奇待匹配点， 即（i + j）为odd


(资料图片仅供参考)

将匹配点向相邻匹配点连边，建 S 和 T 超级源汇， 将 S 与奇待匹配点连边， 偶待匹配点与T连边

容量皆为1， 跑一边最大流，最后检查与S, T 相连的 ‘2’ 边是否都为零即可。

可惜的是，这种思路只能过赛时数据，被after-contest hack掉了， 这里提供一组数据

Input

4 411?1?22212111?11

Output

Yes

可以看出， 最大流有多种情况， 2与2 的方格不一定能连边

所以只能跑一遍有源汇上下界可行流了。

关于上下界可行流可以看这篇Blog

#include #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 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 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" <

Solution 二分图最大匹配

原先的最大流思路真的不行吗?

如果我们跳出网络流是个天然二分图这个思路， 重新建图，另辟蹊径，即是柳暗花明。

我们知道，原先的想法只是卡在达到最大匹配数但是不是所有的2都被匹配。我们是不是可以交换一些"?"与"2"的匹配， 转而变成"2"与’2‘ 的匹配，我看到洛谷上有大神已经怎么写的了，他是不断寻找增广路， 使得每一个’2‘都尽可能被匹配，在此%%%。

也可以重新建图，求出最大匹配， 然后看匹配数是否等于2的个数即可

#include #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 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 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" <

关键词：