文章目錄

• 例題：
• • NC20483 [ZJOI2009]假期的宿舍
  • • 題目描述：
    • 題解：
  • NC51316 Going Home
  • • 題目描述：
    • 題解：
  • NC107638 poj3041 Asteroids
  • • 題目描述：
    • 題解：
  • NC20472 [ZJOI2007]矩陣游戲
  • • 題目描述：
    • 題解：
  • NC110335 CF387D George and Interesting Graph
  • • 題目：
    • 題解：
    • 代碼：
    • 代碼：
  • NC131152 Gym 101873F Plug It In
  • • 題意：
    • 題解：
    • 代 碼：
  • NC112788 CF981F Round Marriage
  • • 題目：
    • 題解：
    • 答案：

例題：

NC20483 [ZJOI2009]假期的宿舍

題目描述：

學校放假了 · · · · · · 有些同學回家了，而有些同學則有以前的好朋友來探訪，那么住宿就是一個問題。比如 A 和 B 都是學校的學生，A 要回家，而 C 來看B，C 與 A 不認識。我們假設每個人只能睡和自己直接認識的人的床。那么一個解決方案就是 B 睡 A 的床而 C 睡 B 的床。
而實際情況可能非常復雜，有的人可能認識好多在校學生，在校學生之間也不一定都互相認識。我們已知一共有 n 個人，并且知道其中每個人是不是本校學生，也知道每個本校學生是否回家。
問是否存在一個方案使得所有不回家的本校學生和來看他們的其他人都有地方住。

題解：

構造二分圖
一邊是
本校學生有相應的床
一邊是
要到學校的人
床與人構造邊

? 左集合為所有需要床的人，右集合為所有的床
? 當第x個人可以睡第y張床（即認識第y個床的主人）那么就可以連邊
? 求出最大匹配即可
詳細題解+代碼看

NC51316 Going Home

題目描述：

n 個小人回到 n 間房子，要求一對一，告訴每個人的位置和每個房子的位置，問n個人移動的總距離最少是多少

題解：

最小權值匹配模板

將所有值取相反數，然后跑一遍最優權值匹配模板

NC107638 poj3041 Asteroids

題目描述：

網格圖中有若干個隕石，每次發射武器可以打掉某一行或某一列的所有隕石，求打完所有隕石的最少次數

題解：

首先，貪心的打星球最多的行/列有反例，如：
0 0 0 0
1 1 0 0
1 0 1 0
1 0 0 1
正解：
我們把行和列抽象為點，把隕石抽象為邊，即當（x,y）有一個隕石的時候 ，將左邊的第x個
點與右邊的第y個點連邊
? 最后是要找到最少的點（行/列）來覆蓋掉所有的邊（隕石）
? 也就是二分圖的最小點覆蓋！
最小點覆蓋：在二分圖中選盡量少的點覆蓋所有的邊
我們將問題轉化為選左右最少數量的點可以覆蓋所有邊
而 最小點覆蓋=最大匹配

比如例子：
0 0 0 0
1 1 0 0
1 0 1 0
1 0 0 1

NC20472 [ZJOI2007]矩陣游戲

題目描述：

? 小Q是一個非常聰明的孩子，除了國際象棋，他還很喜歡玩一個電腦益智游戲——矩陣游戲。
矩陣游戲在一個N *N黑白方陣進行（如同國際象棋一般，只是顏色是隨意的）。
? 每次可以對該矩陣進行兩種操作：
? 行交換操作：選擇 矩陣的任意兩行，交換這兩行（即交換對應格子的顏色）
? 列交換操作：選擇矩陣的任意行列，交換這兩列（即交換 對應格子的顏色）
? 游戲的目標，即通過若干次操作，使得方陣的主對角線(左上角到右下角的連線)上的格子均為黑色。
? 對于某些關卡，小Q百思不得其解，以致他開始懷疑這些關卡是不是根本就是無解的！！于是小Q決定寫一個程序來判斷這些關卡是否有解。
? N<=200

題解：

問題可以轉化成：
? 每一行只保留一個黑色的點，且讓這些黑色的點所在的列各不相同（即覆蓋到每一列）
? 把行列抽象成點，分別為左集合和右集合
? 把黑點抽象成邊，連接對應的行和列
? 看最大匹配是不是等于n，如果等于n就可行

NC110335 CF387D George and Interesting Graph

題目：

給你一個無重邊的有向圖，你每次操作可以加一條邊或者刪一條邊，求讓圖變成一個“有趣
圖”的最小操作次數
? “有趣圖”，滿足：
? 存在一個中心結點v，它和其他每個點都有雙向邊，且和自身有自環。
? 除了中心結點之外，其他結點的入度和出度都為2。 ? 2 ≤ n ≤ 500, 1 ≤ m ≤ 1000

題解：

題目要求的其他節點的入度和出度都為2，因為中心節點要與其他點都有一條邊，去除中心節點 v之后（以及v所關聯的邊），剩下所有點組成環（一個或者多個不想交的環，因為環上的點入度出度都為1）
N不大，考慮枚舉中心點u ? 分類討論：
? 和u有關的邊：
? u的自環 ——沒有就+1條，有就不管了
? u到每一個點的出邊和入邊——如果沒有就加上這1條，如果有就不管

和u無關的邊

將每個點的入度與出度分為左集合和右集合

? 當我們把和u有關的邊都刪掉以后，每個點的出度和入度都應該是1 ? 在這種情況下我們要操作的次數最小，也就是保留盡量多的原來的邊——把每個點拆成
入點和出點，所有的入點和出點分別為左集合和右集合，求出來的最大匹配就是能保留
的邊，其他的邊要刪掉；而如果最大匹配數不等于非中心節點數，顯然就還需要加邊
（需要將二分圖匹配加成滿配才能滿足每個點入度1出度1，這樣原圖也就變成了一個環或者多個不相交的環。）

代碼：

目前為WA，沒發現哪里錯了。。。感覺應該沒問題的

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=600; const int mod=500; int g[maxn][maxn]; int a[1030][1030]; int tot=0; int vis[maxn]; int link[maxn]; int n,m; int maxmatch(int x) {for(int i=1+n;i<=n+n;i++){if(a[x][i]==0||vis[i])continue;vis[i]=1;if(link[i]==0||maxmatch(link[i])){link[i]=x;return 1;}}return 0; } int main() {cin>>n>>m;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;g[x][y]=1;}int maxx=0x7f;for(int i=1;i<=n;i++){memset(link,0,sizeof(link));tot=0;if(g[i][i]!=1)tot++;for(int j=1;j<=n;j++){if(j==i)continue;if(g[i][j]==0)tot++;if(g[j][i]==0)tot++;} int sum=0;int ans=0;for(int j=1;j<=n;j++){if(j==i)continue;for(int k=1;k<=n;k++){if(k==i)continue;if(g[j][k]){a[j][k+n]=1;a[k+n][j]=1;ans++;}}}//int op=0;for(int j=1;j<=n;j++){if(j==i)continue;memset(vis,0,sizeof(vis));sum+=maxmatch(j);}tot+=ans-sum;tot+=n-1-sum;maxx=min(maxx,tot);}cout<<maxx; }

網上找的AC代碼：

#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int match[600]; int vis[600]; int a[600][600]; int x[4545]; int y[4545]; int n,m; int find(int u) {for(int i=1;i<=n;i++){if(a[u][i]==1&&vis[i]==0){vis[i]=1;if(match[i]==-1||find(match[i])){match[i]=u;return 1;}}}return 0; } int Slove(int u) {int ans=0,tot=0;memset(a,0,sizeof(a));for(int i=1;i<=m;i++)a[x[i]][y[i]]=1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][j]==1&&(i!=u)&&(j!=u))tot++;if(a[i][j]==0&&(i==u||j==u)){ans++;}if(i==u||j==u)a[i][j]=0;}}memset(match,-1,sizeof(match));int output=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(i==u)continue;if(find(i))output++;}ans+=n-1-output;ans+=tot-output;return ans; } int main() {while(~scanf("%d%d",&n,&m)){for(int i=1;i<=m;i++){scanf("%d%d",&x[i],&y[i]);}int ans=0x3f3f3f3f;for(int i=1;i<=n;i++){int tmp=Slove(i);ans=min(ans,tmp);}printf("%d\n",ans);} }

代碼：

NC131152 Gym 101873F Plug It In

評測地址

題意：

有m個插座，n個電器，每個插座最多可連接一個電器。另外有一個插線板，可以使得一個插座連接三個電器，給出每個插座能插的電器，問最多能插電器的個數是多少。
? N,m<=1500, k(邊數)<=75000

題解：

先不考慮插線板 ——二分圖最大匹配
? 插線板會使得某個插頭被復制兩份
? ——枚舉插頭然后加倍再跑最大匹配行不行？
? 會tle
? 因為插一個插頭其實只是加了兩個點——先把原圖的最大匹配結果保留下來
? 然后每次在這個結果上加兩個點，給它兩找增廣路即可。

代 碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=1508; int a[maxn][maxn]; int vis[maxn]; int link[maxn]; int link1[maxn]; int n,m,k; int maxmatch(int x) {for(int i=1;i<=m;i++){if(vis[i]||a[x][i]==0)continue;vis[i]=1;if(link[i]==0||maxmatch(link[i])){link[i]=x;return 1;}}return 0; } void init() {for(int i=1;i<=m;i++){link[i]=link1[i];} } int main() {cin>>n>>m>>k;//while(scanf("%d%d%d", &n, &m, &k) == 3){for(int i=1;i<=k;i++){int x,y;cin>>x>>y;a[x][y]=1;//a[y][x]=1;}int sum=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));sum+=maxmatch(i);}// cout<<"sum="<<sum<<endl;int maxx=0;for(int i=1;i<=m;i++){link1[i]=link[i];}for(int i=1;i<=n;i++){init();int tot=0;for(int j=1;j<=2;j++){memset(vis,0,sizeof(vis));tot+=maxmatch(i);}maxx=max(maxx,tot);//cout<<"tot="<<tot<<endl;// cout<<"sum="<<sum<<endl;}cout<<sum+maxx<<endl;}}

NC112788 CF981F Round Marriage

題目：

? n個新郎和n個新娘圍成一個環，環的長度為L，給出所有新郎可以站的位置和新娘可以站的位置，將新郎新娘安排到這些位置上，最 小化每一對新郎和新娘距離的最大值。
? 1≤n≤2*10⁵ ，1 ≤ L≤ 10⁹

題解：

? 二分答案
? 每次只添加男女之間不超過mid的邊，求最大匹配
? 會tle
? Hall定理：對于一個二分圖，如果對于左邊任意子集S，其對應邊連接了一個右邊的點集T，
都有|S|≤|T|，那么這個二分圖有完美匹配。(充要)

對于本題來說，左集合的點x，在右集合能匹配的點剛好是一個區間，記為[Lx,Rx] ? 因為當x增大的時候，對應的區間也是右移的，所以我們只需要看連續的左集合——左集合中
任意區間[a,b]都需要滿足其對應區間[La，Rb]中的元素比他多
? 即b-a<=Rb-La
? 移項： b-Rb<=a-La
sum[b]:b點及以前新郎個數
sum2[b]：b點及以前新娘個數
x是第幾個新郎，Lx，Ly是新娘的范圍
再枚舉a，b

二分答案，判mid是否合法
如何判斷：如果是在直線上，那么遍歷匹配即可
現在在環上，即既可以向前匹配也可以向后匹配，那么將環拆開，擴展成三倍

顯然a和b的匹配邊是不可能交叉的，因為交叉必定沒有不交叉優
hall定理：二分圖兩個點集A,B，連續一段A的點對應連續一段B的點的 充要條件是 這些點對的匹配邊之間不交叉
重要推論：二部圖G中的兩部分頂點組成的集合分別為X,Y, 若|X|=|Y|,
且G中有一組無公共端點的邊，一端恰好組成X中的點，一端恰好組成Y中的點，則稱二部圖G中存在完美匹配

有了這個定理，就可以用在判定上：a的點集對應b點集的連續一段，即b的n個點也是連續的，因為之前已經確定匹配邊不交叉
先求出a[1]的范圍[a[1]-mid,a[1]+mid]對應的能控制的b數組的范圍[l1,r1]
那么a[2]的控制范圍要和[l1+1,r1+1]交叉得到[l2,r2]
那么a[3]的控制范圍要和[l2+1,r2+1]交叉得到[l3,r3]

…依次類推
可以這個區間長度只會減小不會變大

答案：

#include<bits/stdc++.h> using namespace std; #define maxn 200005 long long n,L,a[maxn],b[maxn<<2],c[maxn],m;int judge(int mid){//a[i]的控制區間是[a[i]-mid,a[i]+mid] int l=1,r=m;for(int i=1;i<=n;i++){while(a[i]-mid>b[l])++l;while(a[i]+mid<b[r])--r;if(l>r)return 0;++l,++r;} return 1; }int main(){cin>>n>>L;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>c[i];sort(c+1,c+1+n);sort(a+1,a+1+n);for(int i=1;i<=n;i++)b[i]=c[i]-L;for(int i=1;i<=n;i++)b[i+n]=c[i];for(int i=1;i<=n;i++)b[i+2*n]=c[i]+L;m=3*n;int l=0,r=L,ans,mid;while(l<=r){mid=l+r>>1;if(judge(mid))ans=mid,r=mid-1;else l=mid+1;}cout<<ans<<'\n'; }

總結

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

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