定義
二分圖：可以把點(diǎn)集分為兩部分\(A,B\),其中\(A\)，\(B\)內(nèi)部不存在連邊的圖
二分圖的確立，當(dāng)且僅當(dāng)圖中不存在奇環(huán)
Pf：黑白染色
概念：
- 匹配：\(A,B\)一一對(duì)應(yīng)，不存在相鄰的邊的邊集
- 點(diǎn)覆蓋：點(diǎn)集\(S\)滿足每條邊至少存在一點(diǎn)位于\(S\)
- 獨(dú)立集：點(diǎn)集\(S\)滿足每條邊至多存在一點(diǎn)位于\(S\)
- 邊覆蓋：邊集\(E\)滿足每個(gè)頂點(diǎn)至少存在一條邊位于\(E\)
- 路徑覆蓋（鏈）：在圖中找路徑使得每個(gè)節(jié)點(diǎn)在一條路徑上
- 團(tuán)：點(diǎn)集\(S\)滿足其中所有點(diǎn)都相互連通
- 反鏈：點(diǎn)集\(S\)滿足\(S\)中所有點(diǎn)互不聯(lián)通
匈牙利
求二分圖中最大匹配
bool dfs(int u) {
for(auto v:V[u]) {
if(fl[v]!=lim) {
fl[v]=lim;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
時(shí)間復(fù)雜度\(O(nm)\)
増廣路
（虛邊表示非匹配邊，實(shí)邊表示匹配邊）
其中最后圖上的増廣路必須滿足匹配邊>=非匹配邊（否則會(huì)有空余的邊，這不是最大匹配）
特殊的情況：從非匹配點(diǎn)開始走到的都是匹配點(diǎn)，非匹配邊-匹配邊交叉（正好為偶數(shù)條邊）
常見關(guān)系：
|最大匹配|=|最小點(diǎn)覆蓋|
Pf:如果除最大匹配外還存在某條邊沒被覆蓋，顯然匹配數(shù)應(yīng)+1，所以最大匹配是點(diǎn)覆蓋，故|最大匹配|>=|最小點(diǎn)覆蓋|
匹配的定義告訴我們，覆蓋的邊和邊之間沒有交點(diǎn)，所以不可能存在更小的點(diǎn)覆蓋，即證
最小點(diǎn)覆蓋的方案構(gòu)造：先求出最大匹配，從左邊未匹配點(diǎn)開始，走未匹配邊到右邊匹配點(diǎn)（一定是），走匹配邊到左邊的匹配點(diǎn)...沿著路徑打標(biāo)記
左邊點(diǎn)集中未出現(xiàn)的點(diǎn)和右邊點(diǎn)集中出現(xiàn)的點(diǎn)是最小點(diǎn)覆蓋
說明：一個(gè)圖可以被分成若干條増廣路，而増廣路有兩種情況
 
前者（存在未匹配點(diǎn)）統(tǒng)計(jì)右節(jié)點(diǎn)優(yōu)，后者為了方便統(tǒng)計(jì)左節(jié)點(diǎn)
點(diǎn)覆蓋與獨(dú)立集對(duì)應(yīng)互補(bǔ)，最大獨(dú)立集=G-最小點(diǎn)覆蓋
Pf：由定義可以發(fā)現(xiàn)
對(duì)于不存在孤立點(diǎn)的圖，|最大匹配|+|最小邊覆蓋|=|V|
Pf:不妨設(shè)節(jié)點(diǎn)數(shù)為\(n\),最大匹配數(shù)為\(m\)
一條邊至多覆蓋2個(gè)節(jié)點(diǎn)，所以顯然要將匹配邊全覆蓋，之后剩下的節(jié)點(diǎn)只能有一條邊逐一覆蓋
則\(2m+t=n,m+t=|\text{最小邊覆蓋}|\)，即證
構(gòu)造：同上
最大團(tuán)=補(bǔ)圖的最大獨(dú)立集
Pf 定義
|最小不可重鏈覆蓋|=n-|最大匹配|
Pf：開始時(shí)每個(gè)點(diǎn)裂成入點(diǎn)和出點(diǎn)，把每個(gè)點(diǎn)看作一條鏈，每次匹配入點(diǎn)和出點(diǎn)（即連邊合并），鏈會(huì)減1，即證
最小可重鏈覆蓋可以轉(zhuǎn)化為最小不可重鏈覆蓋
將點(diǎn)\(i\)能到達(dá)的所有點(diǎn)都與\(i\)相連即可（最優(yōu)的情況下，每個(gè)點(diǎn)只需要經(jīng)過一次）
|最長(zhǎng)反鏈|=|最小可重鏈覆蓋|
最長(zhǎng)反鏈方案構(gòu)造：先按上述求出最大獨(dú)立集，再求出入點(diǎn)和出點(diǎn)都在最大獨(dú)立集上的點(diǎn)
解題思路：
難點(diǎn)往往在構(gòu)造二分圖
通常行列，或者沒有奇環(huán)的圖。。。
例題1
消除格子
行列分開，求最小點(diǎn)覆蓋，等于最大匹配
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=505*505;
int n,K,to[M],nxt[M],he[N],cnt,ma[N];
bool fl[N];
inline void add(int u,int v) {
to[++cnt]=v,nxt[cnt]=he[u],he[u]=cnt;
}
bool dfs(int u) {
for(int e=he[u];e;e=nxt[e]) {
int v=to[e];
if(!fl[v-n]) {
fl[v-n]=1;
if(!ma[v-n]||dfs(ma[v-n])) {
ma[v-n]=u; return 1;
}
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&K);
for(int i=1;i<=K;i++) {
int x,y; scanf("%d%d",&x,&y);
add(x,y+n);
}
int ans=0;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans++;
}
printf("%d\n",ans);
return 0;
}
例題2
出租車訂單
根據(jù)能否連載連邊，然后求最小不可重鏈覆蓋
注意>=1這種細(xì)節(jié)
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,a[N],b[N],c[N],d[N],t[N],ma[N];
bool fl[N];
char s[10];
vector<int>V[N];
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
int main(){
int T; scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%s%d%d%d%d",s+1,&a[i],&b[i],&c[i],&d[i]);
int h=(s[1]-'0')*10+s[2]-'0',m=(s[4]-'0')*10+s[5]-'0';
t[i]=h*60+m;
}
for(int i=1;i<=n;i++) {
int tmp=t[i]+abs(c[i]-a[i])+abs(b[i]-d[i]);
V[i].clear();
for(int j=1;j<=n;j++) {
if(i!=j&&t[j]-tmp>=abs(a[j]-c[i])+abs(b[j]-d[i])+1) {
V[i].push_back(j);
}
}
}
memset(ma,0,sizeof(ma));
int ans=n;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans--;
}
printf("%d\n",ans);
}
return 0;
}
例題3
Luogu P1129 [ZJOI2007] 矩陣游戲
首先發(fā)現(xiàn)橫縱互不干擾（隨意換順序）
接著發(fā)現(xiàn)橫縱分開后只需要橫不需要縱，
最后發(fā)現(xiàn)只要不同列都有不同行的1即可
所以行和列拆開，判斷最大匹配是否為\(n\)
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,ma[N];
bool fl[N];
vector<int>V[N];
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
int main(){
int T; scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
V[i].clear();
for(int j=1;j<=n;j++) {
int op; scanf("%d",&op);
if(op) V[i].push_back(j);
}
}
memset(ma,0,sizeof(ma));
int ans=0;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans++;
}
if(ans==n) puts("Yes");
else puts("No");
}
return 0;
}
例題5
Luogu P4136 誰能贏呢？
把圖拆成\(1\times 2\)的骨牌分組，判斷什么時(shí)候是先手開骨牌的頭，還是后手開骨牌的頭，誰開骨牌頭誰輸
可以理解成有一副二分圖，如果某人先手時(shí)不巧從未匹配點(diǎn)開始，他便輸了，因?yàn)橐粗鬀]有點(diǎn)，要么之后所有點(diǎn)都完美匹配了，后手只需要沿著匹配邊走即可
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
scanf("%d",&n);
while(n) {
if(n&1) puts("Bob");
else puts("Alice");
scanf("%d",&n);
}
puts("");
}
例題6
Luogu P4055 [JSOI2009]游戲
多了限制，另外讓你求初始點(diǎn)
由上題可以發(fā)現(xiàn)，先手下在某個(gè)最大匹配的未匹配點(diǎn)上，之后后手無論往哪兒走，始終落在存在匹配邊的匹配點(diǎn)上，先手只需要沿著匹配邊走即可
而如果先手下的位置一定是匹配點(diǎn)，那么后手只需要沿匹配邊走即可，因?yàn)橄仁譄o論如何都會(huì)落在存在匹配邊的匹配點(diǎn)上
所以考慮如何找最大匹配的未匹配點(diǎn)求并
只需要從每個(gè)未匹配點(diǎn)開始訪問増廣路，訪問到的節(jié)點(diǎn)都可以成為最大匹配的未匹配點(diǎn)
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int n,m,ma[N];
bool fl[N],ans[N];
char s[105][105];
vector<int>V[N];
inline int id(int i,int j) {
return (i-1)*m+j;
}
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
void dgs(int u) {
ans[u]=1;
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1; dgs(ma[v]);
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(i+j&1&&s[i][j]=='.') {
if(s[i-1][j]=='.') {
V[id(i,j)].push_back(id(i-1,j));
}
if(s[i][j-1]=='.') {
V[id(i,j)].push_back(id(i,j-1));
}
if(s[i+1][j]=='.') {
V[id(i,j)].push_back(id(i+1,j));
}
if(s[i][j+1]=='.') {
V[id(i,j)].push_back(id(i,j+1));
}
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) {
if(i+j&1&&s[i][j]=='.') {
memset(fl,0,sizeof(fl));
dfs(id(i,j));
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
V[id(i,j)].clear();
if(!(i+j&1)&&ma[id(i,j)]) {
ma[ma[id(i,j)]]=id(i,j);
}
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(i+j&1&&s[i][j]=='.') {
if(s[i-1][j]=='.'&&id(i-1,j)!=ma[id(i,j)]) {
V[id(i,j)].push_back(id(i-1,j));
V[id(i-1,j)].push_back(id(i,j));
}
if(s[i][j-1]=='.'&&id(i,j-1)!=ma[id(i,j)]) {
V[id(i,j)].push_back(id(i,j-1));
V[id(i,j-1)].push_back(id(i,j));
}
if(s[i+1][j]=='.'&&id(i+1,j)!=ma[id(i,j)]) {
V[id(i,j)].push_back(id(i+1,j));
V[id(i+1,j)].push_back(id(i,j));
}
if(s[i][j+1]=='.'&&id(i,j+1)!=ma[id(i,j)]) {
V[id(i,j)].push_back(id(i,j+1));
V[id(i,j+1)].push_back(id(i,j));
}
}
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
memset(fl,0,sizeof(fl));
if(s[i][j]=='.'&&!ma[id(i,j)]) {
dgs(id(i,j));
}
}
}
bool fll=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(ans[id(i,j)]) {
if(!fll) puts("WIN");
fll=1;
printf("%d %d\n",i,j);
}
}
}
if(!fll) puts("LOSE");
return 0;
}
例題7
Luogu P2172 [國(guó)家集訓(xùn)隊(duì)]部落戰(zhàn)爭(zhēng)
先來證明：像馬一樣在網(wǎng)格圖上跳躍形成的軌跡為二分圖,即只存在偶環(huán)
Pf: 假設(shè)從\((0,0)\)開始，每次\(+-(a,b)\),\(+-(b,a),a>0,b>0\)
不妨設(shè)\(x(a,b)+y(b,a)=(0,0)\),則
\[\left\{
\begin{array}{c}
ax+by=0 \\
bx+ay=0
\end{array}
\right.
\] 相加發(fā)現(xiàn)：
\[(a+b)(x+y)=0
\] 則：
\[x+y=0
\] 所以只存在偶環(huán)
求最小不可重路徑覆蓋即可
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int n,m,r,c,ma[N];
bool fl[N];
char s[N][N];
vector<int>V[N];
inline int id(int x,int y) {
return (x-1)*m+y;
}
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
int main() {
scanf("%d%d%d%d",&n,&m,&r,&c);
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(s[i][j]=='.'){
if(s[i+r][j+c]=='.') {
V[id(i,j)].push_back(id(i+r,j+c));
}
if(s[i+c][j+r]=='.'){
V[id(i,j)].push_back(id(i+c,j+r));
}
if(j-c>0&&s[i+r][j-c]=='.') {
V[id(i,j)].push_back(id(i+r,j-c));
}
if(j-r>0&&s[i+c][j-r]=='.'){
V[id(i,j)].push_back(id(i+c,j-r));
}
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) {
if(s[i][j]=='.') {
ans++;
memset(fl,0,sizeof(fl));
if(dfs(id(i,j))) ans--;
}
}
}
printf("%d\n",ans);
return 0;
}
例題8
幻燈片
建立二分圖后判斷是否可以有多解
法1：暴力刪除邊后判斷答案是否相同
法2：對(duì)每條匹配邊建反邊（提供反悔機(jī)會(huì)），在殘余網(wǎng)絡(luò)上查找是否存在環(huán)，如果存在說明有多解
有向圖判斷具體的環(huán)，只能tarjan
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,ma[N],to[N],x[N],y[N],x1[N],t1[N],x2[N],y2[N],dfn[N],low[N],st[N],top,co[N],col,cnt;
bool fl[N];
vector<int>V[N];
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
void tar(int u) {
dfn[u]=low[u]=++cnt; st[++top]=u;
for(auto v:V[u]) {
if(!dfn[v]) {
tar(v),low[u]=min(low[u],low[v]);
} else if(!co[v]) {
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]) {
co[u]=++col;
while(st[top]!=u) {
co[st[top]]=col; top--;
}
top--;
}
}
int main(){
scanf("%d",&n); int id=0;
while(n) {
printf("Heap %d\n",++id);
for(int i=1;i<=n;i++) {
scanf("%d%d%d%d",&x1[i],&x2[i],&t1[i],&y2[i]);
}
for(int i=1;i<=n;i++) {
scanf("%d%d",&x[i],&y[i]);
V[i].clear();
for(int j=1;j<=n;j++) {
if(x1[j]<x[i]&&x[i]<x2[j]&&t1[j]<y[i]&&y[i]<y2[j]) {
V[i].push_back(j);
}
}
}
memset(ma,0,sizeof(ma));
int ans=0;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans++;
}
/*if(ans!=n) {
puts("none");
} else */{
for(int i=1;i<=n+n;i++) {
V[i].clear();
}
for(int i=1;i<=n;i++) {
to[ma[i]]=i; V[i+n].push_back(ma[i]);
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(to[i]!=j&&x1[j]<x[i]&&x[i]<x2[j]&&t1[j]<y[i]&&y[i]<y2[j]) {
V[i].push_back(j+n);
}
}
}
memset(dfn,0,sizeof(dfn));
memset(co,0,sizeof(co));
col=0; top=0; cnt=0;
for(int i=1;i<=n+n;i++) {
if(!dfn[i]) tar(i);
}
bool fll=0;
for(int i=1;i<=n;i++) {
if(co[ma[i]]!=co[i+n]) {
printf("(%c,%d) ",i+'A'-1,ma[i]);
fll=1;
}
}
if(!fll) {
puts("none");
} else puts("");
}
scanf("%d",&n);
}
return 0;
}
例題9
模板集合
只能有一個(gè)“*”,所以將所有可能的01子串處理出
將可能合并的子串用邊相連，只會(huì)有一個(gè)位置不同，所以可以按01子串中1的個(gè)數(shù)的奇偶性分成二分圖
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int n,m,ma[N];
bool fl[N],num[N],t[N];
char s[N];
vector<int>V[N];
inline int id(int x,int y) {
return (x-1)*m+y;
}
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
int main() {
scanf("%d%d",&m,&n);
for(int i=1;i<=1023;i++) {
num[i]=num[i>>1]^(i&1);
}
while(n||m) {
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++){
scanf("%s",s+1);
int t1=0,t2=-1;
for(int j=1;j<=m;j++) {
if(s[j]=='*') {
t1<<=1,t2=t1|1;
} else {
t1=(t1<<1)|(s[j]=='1');
if(t2!=-1) {
t2=(t2<<1)|(s[j]=='1');
}
}
}
t[t1]=1;
if(t2!=-1) t[t2]=1;
}
for(int i=1;i<=1023;i++) {
V[i].clear();
}
for(int i=0;i<=1023;i++){
if(t[i])
for(int j=1;j<=m;j++) {
if((i&(1<<j-1))==0) {
int k=i|(1<<j-1);
if(t[k]) {
if(num[i]) {
V[i].push_back(k);
} else {
V[k].push_back(i);
}
}
}
}
}
int ans=0;
memset(ma,0,sizeof(ma));
for(int i=0;i<=1023;i++){
if(t[i]) ans++;
if(t[i]&&num[i]) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans--;
}
}
printf("%d\n",ans);
scanf("%d%d",&m,&n);
}
return 0;
}
例題10
男孩女孩
求最大團(tuán)
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,m,K,f[N][N],ma[N];
bool fl[N];
vector<int>V[N];
bool dfs(int u) {
for(auto v:V[u]) {
if(!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
int main(){
scanf("%d%d%d",&n,&m,&K); int id=0;
while(n||m||K) {
id++; printf("Case %d: ",id);
memset(f,0,sizeof(f));
for(int i=1;i<=K;i++) {
int u,v; scanf("%d%d",&u,&v);
f[u][v]=1;
}
for(int i=1;i<=n;i++) {
V[i].clear();
for(int j=1;j<=m;j++) {
if(!f[i][j]) {
V[i].push_back(j);
}
}
}
memset(ma,0,sizeof(ma));
int ans=n+m;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans--;
}
printf("%d\n",ans);
scanf("%d%d%d",&n,&m,&K);
}
return 0;
}
例題 11
Luogu P4298 [CTSC2008]祭祀
最長(zhǎng)反鏈=最小可重路徑覆蓋
第一問，第二問，KO
第三問：將該點(diǎn)和其關(guān)的所有點(diǎn)刪掉，如果該點(diǎn)可能成為祭點(diǎn)，則反鏈數(shù)量會(huì)減少1，再來一遍即可
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,f[N][N],ma[N];
bool fl[N],vis[N<<1],to[N],ban[N];
vector<int>V[N],V1[N];
bool dfs(int u) {
if(ban[u]) return 0;
for(auto v:V[u]) {
if(!ban[v]&&!fl[v]) {
fl[v]=1;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
void dgs(int u) {
vis[u]=1;
for(auto v:V[u]) {
if(!fl[v]){
fl[v]=1;
vis[v+n]=1;
dgs(ma[v]);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
int u,v; scanf("%d%d",&u,&v);
f[u][v]=1;
}
for(int k=1;k<=n;k++) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(f[i][k]&&f[k][j]) f[i][j]=1;
}
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(f[i][j]) {
V[i].push_back(j);
V1[j].push_back(i);
}
}
}
int ans=n;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) ans--;
}
printf("%d\n",ans);
for(int i=1;i<=n;i++) to[ma[i]]=1;
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(!to[i]) dgs(i);
}
for(int i=1;i<=n;i++) {
printf("%d",vis[i]&(!vis[i+n]));
}
puts("");
for(int i=1;i<=n;i++) {
int res=n;
memset(ban,0,sizeof(ban));
for(int j=1;j<=n;j++) {
if(f[i][j]||f[j][i]||i==j) {
ban[j]=1;
res--;
}
}
memset(ma,0,sizeof(ma));
for(int i=1;i<=n;i++) {
memset(fl,0,sizeof(fl));
if(dfs(i)) res--;
}
printf("%d",res==ans-1);
}
return 0;
}
例題12
Luogu P3231 [HNOI2013]消毒
考慮2維：對(duì)于\((a,b)\)的代價(jià)\(min(a,b)\)，可以看出消去\(a\)次行，或者消去\(b\)次列
所以可以將行列分開做，二分圖
再加1維，沒有三分圖這種東西，發(fā)現(xiàn)最小的一維最大為17，所以暴力枚舉最小一維怎么刪的狀態(tài)，將沒被刪的疊在一起，看作2維
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int n,ma[N],lim,a[N],b[N],c[N],fl[N];
vector<int>V[N];
bool dfs(int u) {
for(auto v:V[u]) {
if(fl[v]!=lim) {
fl[v]=lim;
if(!ma[v]||dfs(ma[v])) {
ma[v]=u; return 1;
}
}
}
return 0;
}
int main(){
// freopen("1.in","r",stdin);
int T; scanf("%d",&T);
while(T--) {
scanf("%d%d%d",&a[0],&b[0],&c[0]);
int ans=1e9; n=0;
for(int i=1;i<=a[0];i++) {
for(int j=1;j<=b[0];j++) {
for(int k=1;k<=c[0];k++) {
int op; scanf("%d",&op);
if(op) {
a[++n]=i,b[n]=j,c[n]=k;
}
}
}
}
if(a[0]>=b[0]&&b[0]<=c[0]) swap(a,b);
if(a[0]>=c[0]&&b[0]>=c[0]) swap(b,c);
for(int i=0;i<(1<<a[0]);i++) {
memset(fl,0,sizeof(fl));
memset(ma,0,sizeof(ma));
int res=0;
for(int j=1;j<=n;j++) {
if(!(i&(1<<a[j]-1))) V[b[j]].push_back(c[j]);
}
for(int j=1;j<=a[0];j++) {
if(i&(1<<j-1)) res++;
}
for(int j=1;j<=b[0];j++) {
lim=j;
if(dfs(j)) res++;
}
ans=min(ans,res);
for(int j=1;j<=n;j++) {
V[b[j]].clear();
}
}
printf("%d\n",ans);
}
return 0;
}
|
