这两天自己看书学了下二分图的最大匹配，也做了挺多题，感觉算是会了
于是 尽情地享受我的口胡吧~
//大神请右上角
二分图是一种图，但其顶点可以分成两个集合X和Y，其中X或Y中任意两个顶点在同一集合中的点都不相连，所有的边关联在两个顶点中，恰好一个属于集合Ｘ，另一个属于集合Ｙ。
给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。图中包含边数最多的匹配称为图的最大匹配
求二分图匹配就我所知有两种方法，第一种是网络流算法，第二种是匈牙利算法；
由于该日志讲的是二分图的最大匹配问题，所以这里我只说下匈牙利算法~~~
首先要明确一个概念。。即增广轨（tmd这是什么东西？！！ ）
若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。
所以匈牙利算法的核心依据就是找增广轨~
下面给出流程：
算法的思路是不停的找增广路径, 并增加匹配的个数,增广路径顾名思义是指一条可以使匹配数变多的路径，在匹配问题中,增广路径的表现形式是一条"交错路径"，也就是说这条由图的边组成的路径， 它的第一条边是目前还没有参与匹配的，第二条边参与了匹配，第三条边没有..最后一条边没有参与匹配，并且始点和终点还没有被选择过。这样交错进行，显然他有奇数条边。那么对于这样一条路径，我们可以将第一条边改为已匹配，第二条边改为未匹配...以此类推。也就是将所有的边进行"反色"，容易发现这样修改以后，匹配仍然是合法的，但是匹配数增加了一对。另外，单独的一条连接两个未匹配点的边显然也是交错路径。可以证明。当不能再找到增广路径时，就得到了一个最大匹配，这也就是匈牙利算法的思路。
// 以上，转
下面来通过例题理解
2776 寻找代表元
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 Description
绍一中一共有n个社团，分别用1到n编号。
绍一中一共有m个人，分别用1到m编号。每个人可以参加一个或多个社团，也可以不参加任何社团。
每个社团都需要选一个代表。豆豆希望更多的人能够成为代表。
输入描述 Input Description
第一行输入两个数n和m。
以下n行每行若干个数，这些数都是不超过m的正整数。其中第i行的数表示社团i的全部成员。每行用一个0结束。
输出描述 Output Description
输出最多的能够成为代表的人数。
样例输入 Sample Input
4 4
1 2 0
1 2 0
1 2 0
1 2 3 4 0
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
各个测试点1s
数据范围
n,m<=200
//RxD：啊，这种傻屌题 是水的呀
好吧，先构图，再跑最大流，呸，匈牙利
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int map[300][300],link[300],y[300],n,m,x,q;
bool find(int v){
for(int i=1;i<=m;i++)
if(map[v][i]&&!y[i]){
y[i]=1;
if(!link[i]||find(link[i])){
link[i]=v;
return 1;
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&m);
memset(map,0,sizeof(map));
for(int i=1;i<=n;i++){
int xx;
for(int j=1;j<=m;j++){
scanf("%d",&xx);
if(xx!=0)map[i][xx]=1;
else break;
}
}
int ans=0;
for(int i=1;i<=n;i++){
memset(y,0,sizeof(y));
if(find(i))++ans;
}
printf("%d",ans);
}
然后再来一题~
3052 多米诺
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 钻石 Diamond
题目描述 Description
一个矩形可以划分成M*N个小正方形，其中有一些小正方形不能使用。一个多米诺骨牌占用两个相邻的小正方形。试问整个区域内最多可以不重叠地放多少个多米诺骨牌且不占用任何一个被标记为无法使用的小正方形。
输入描述 Input Description
第一行有两个用空格隔开的正整数M和N。
第二行有一个正整数K，表示共有K个小正方形不能使用。输入数据保证K<=M*N。
以下K行每行有两个用空格隔开的数X和Y，表示第X行的第Y个小正方形不能使用。
输出描述 Output Description
输出最多能放多少个多米诺骨牌。
样例输入 Sample Input
3 3
2
1 1
2 2
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
对于30%的数据，M=1；
对于50%的数据，M<=2；
对于70%的数据，M<=3；
对于100%的数据，M<=50，N<=50。
//浩如烟海：靠，这题tm怎么做，匹配不了啊
这题。。构图，网络流啊呸，先黑白染色再跑匈牙利
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int f[10001][5],link[10001],y[10001],a[10001],ans,n,m,i,j;
bool find(int v){
for(int i=1;i<=f[v][0];i++){
int j=f[v][i];
if((!a[j])&&(!y[j])){
y[j]=1;
if(!link[j]||find(link[j])){
link[j]=v;
return 1;
}
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&m);
int kk=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if((i+j)%2){
int z=(i-1)*m+j;
if(z%m!=0)f[z][++f[z][0]]=z+1;
if(z%m==0||z%m>1)f[z][++f[z][0]]=z-1;
if(z>m)f[z][++f[z][0]]=z-m;
if(z<=(n-1)*m)f[z][++f[z][0]]=z+m;
}
int k;
memset(a,0,sizeof(a));
scanf("%d",&k);
for(int i=1;i<=k;i++){
int xx,yy;
scanf("%d%d",&xx,&yy);
a[(xx-1)*m+yy]=1;
}
memset(link,0,sizeof(link));
ans=0;
for(int i=1;i<=n*m;i++)
if(!a[i]){
memset(y,0,sizeof(y));
if(find(i))++ans;
}
printf("%d\n",ans);
}
loading...
评论 (0)
