之前一直把矩陣的元素以為是給定的\(m\)以內… 然后才發現…

? 嗶了狗了…

? 二分圖匹配咯… 如果第\(i\)行第\(j\)列是黑色，那么在代表這一行和這一列的兩個節點之間連邊。然后匈牙利算法跑一遍，判斷最大匹配是否是\(n\)即可。有若干種想法可以證明(偽)它的正確性。如果某一組輸入對應的二分圖的最大匹配是\(n\)，那么它一定存在滿足題意的交換方案——就把行列交換想像成節點的交換即可；反過來，如果存在滿足題意的交換方案，那么就把它交換回去，可以發現仍是每一個行節點對應著一個列節點。因此，不難看出這樣做的依據：原先不在同一行的兩個格子，交換之后仍不會在同一行；不在同一列的同理。所以，原問題有解的充要條件就是是否有\(n\)個格子的“行和列的一一對應”，亦即行互不相同且列互不相同。這就顯然是一個二分圖最大基數匹配的模型了。

（為什么傻逼的我總把二分圖染色的paint和匈牙利算法的match搞混…）

（還有一個小細節：是把行和列各單獨建\(2n\)個點呢，還是混在一起建\(n\)個點呢？答案是都可以，——因為這是有向圖，如果出現奇圈，直接環上個各點的\(bel\)值套在一起即可… 很奇怪… 所以還是分開搞吧…）

// BZOJ 1059#include <algorithm> #include <cstdio> #include <cstring> using namespace std;#define rep(i,a,b) for (int i=a; i<=b; i++)#define read(x) scanf("%d", &x)#define fill(a,x) memset(a, x, sizeof(a))const int N = 200+5, M=200*200+5;int T, n, x, m, pre[M], last[N], to[M], bel[2*N];bool used[2*N];void ine(int x, int y) {m++;to[m] = y; pre[m] = last[x]; last[x] = m;}#define reg(i,x) for (int i = last[x]; i; i = pre[i])void init() {m = 0;fill(last, 0);fill(bel, 0);}bool match(int x) {reg(i,x) {int y = to[i];if (used[y]) continue;used[y] = true;if (bel[y]==0 || match(bel[y])) {bel[y] = x;return true;}}return false;}int main() {read(T);while (T--) {read(n);init();rep(i,1,n) rep(j,1,n) {read(x);if (x==1) ine(i, n+j);}bool flag = true;rep(i,1,n) {fill(used, false);if (!match(i)) { puts("No"); flag = false; break; }}if (flag) puts("Yes");}return 0; }

轉載于:https://www.cnblogs.com/yearwhk/p/5140574.html

總結

以上是生活随笔為你收集整理的BZOJ 1059 - 二分图匹配的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。