kuangbin专题十 匹配问题
把最近刷的匹配问题全部放这里算了
应该不会把这个专题刷完
大概率写着写着就鸽了
1.Fire Net HDU - 1045 (二分图匹配 匈牙利算法)
题目思路
二分图匹配的简单题 第一次做没懂怎么建图
看了下题解 发现是对行和列进行缩点
然后对行和列重合的数字建边
再跑匈牙利算法 求值
ac代码
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
using namespace std;
const int maxn = 1e3+10;
const int inf = 0x3f3f3f3f;
const ll llinf =0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
int n,len,sumh,suml;
char a[maxn][maxn];
int h[maxn][maxn];
int l[maxn][maxn];
int first[maxn],used[maxn],girl[maxn];
struct node
{
int to,next;
}e[maxn];
void add(int u,int v)
{
e[len].to=v;
e[len].next=first[u];
first[u]=len++;
}
bool findx(int x)
{
for(int i=first[x];i!=-1;i=e[i].next)
{
int id=e[i].to;
if(used[id]==0)
{
used[id]=1;
if(girl[id]==0||findx(girl[id]))
{
girl[id]=x;
return true;
}
}
}
return false;
}
int main()
{
while(~scanf("%d",&n)&&n)
{
ms(first,-1);len=0;
ms(girl,0);
for(int i=1;i<=n;i++)
{
scanf("%s",a[i]+1);
}
sumh=0,suml=0;
int flag=0;
for(int i=1;i<=n;i++)
{
sumh++;flag=0;
for(int j=1;j<=n;j++)
{
if(a[i][j]=='.')
h[i][j]=sumh,flag=1;
if(a[i][j]=='X')
{
if(flag==1)
sumh++;
h[i][j]=inf;
}
}
}
for(int j=1;j<=n;j++)
{
suml++;flag=0;
for(int i=1;i<=n;i++)
{
if(a[i][j]=='.')
l[i][j]=suml,flag=1;
if(a[i][j]=='X')
{
if(flag==1)
suml++;
l[i][j]=inf;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]!='X')
add(h[i][j],l[i][j]);
}
}
int ans=0;
for(int i=1;i<=sumh;i++)
{
ms(used,0);
if(findx(i))ans++;
}
printf("%d\n",ans);
}
}
2.The Accomodation of Students HDU - 2444 (交叉染色法 二分图匹配)
题目思路
这道题需要判断是否为二分图 学了下交叉染色法判断二分图
会判断二分图后这道题就成了一道模板题了
不过有些细节还是值得学习的
因为我们判断完是二分图后 我们不知道每边有多少个点
我们只是再染色的时候把他们染成了不同的颜色
所以我们在跑匈牙利算法的时候
要判断染的色是否一致
ac代码
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
using namespace std;
const int maxn = 1e3+10;
const int inf = 0x3f3f3f3f;
const ll llinf =0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
int n,m;
vector<int>vec[maxn];
int color[maxn],used[maxn],girl[maxn];
bool dfs(int v,int c)
{
color[v]=c;
for(int i=0;i<vec[v].size();i++)
{
int id=vec[v][i];
if(color[id]==c)
return false;
if(color[id]==0&&!dfs(id,-c))
return false;
}
return true;
}
bool findx(int x)
{
for(int i=0;i<vec[x].size();i++)
{
int id=vec[x][i];
if(used[id]==0)
{
used[id]=1;
if(girl[id]==0||findx(girl[id]))
{
girl[id]=x;
return true;
}
}
}
return false;
}
void solve()
{
ms(color,0);
ms(girl,0);
for(int i=1;i<=n;i++)
{
if(color[i]==0)
{
if(!dfs(i,1))
{
printf("No\n");
return;
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(color[i]==1)
{
ms(used,0);
if(findx(i))ans++;
}
}
printf("%d\n",ans);
}
int main()
{
while(~scanf("%d%d",&n,&m)&&n+m)
{
ms(used,0);
for(int i=1;i<=n;i++)
vec[i].clear();
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
vec[x].push_back(y);
vec[y].push_back(x);
}
solve();
}
}
3.Courses HDU - 1083(二分图匹配 匈牙利算法)
题目思路
这题基本上也是个模板题
套个板子 在判断ans等不等于p就好了
ac代码
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
using namespace std;
const int maxn = 1e3+10;
const int inf = 0x3f3f3f3f;
const ll llinf =0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
int n,m;
vector<int>vec[maxn];
int girl[maxn],used[maxn];
bool findx(int x)
{
for(int i=0;i<vec[x].size();i++)
{
int id=vec[x][i];
if(used[id]==0)
{
used[id]=1;
if(girl[id]==0||findx(girl[id]))
{
girl[id]=x;
return true;
}
}
}
return false;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ms(girl,0);
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d",&x);
for(int j=1;j<=x;j++)
{
scanf("%d",&y);
vec[i].push_back(y);
}
}
int ans=0;
for(int i=1;i<=m;i++)
{
ms(used,0);
if(findx(i))ans++;
}
if(ans==m)
{
printf("YES\n");
}else
{
printf("NO\n");
}
for(int i=1;i<=m;i++)
vec[i].clear();
}
}
;
4.棋盘游戏 HDU - 1281(二分图匹配 删边找重要点)
题目思路
输出的第二个答案很明显 二分图匹配就能得到
但是重要点却不能
我一直以为重要点会有什么特征
想了好久 按照自己的理解写了一发 wa了
看了下别人的思路
竟然就是遍历所有边 把边删了之后 二分图匹配后的答案与原来不同
这个点就是重要点(我常常因为不够暴力而和你们格格不入 菜鸡哭泣)
最好还是用邻接矩阵写 方便删边和复原
不是很明白的是这题为什么不需要像第一题那样缩点
ac代码
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
using namespace std;
const int maxn = 1e3+10;
const int inf = 0x3f3f3f3f;
const ll llinf =0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
int n,m,k;
int mp[maxn][maxn];
int a[maxn][maxn],b[maxn][maxn],used[maxn],girl[maxn];
int g[maxn][maxn];
int sumh,suml,flag;
bool findx(int x)
{
for(int i=1;i<=m;i++)
{
if(mp[x][i]==1)
{
if(used[i]==0)
{
used[i]=1;
if(girl[i]==0||findx(girl[i]))
{
girl[i]=x;
return true;
}
}
}
}
return false;
}
int main()
{
int ce=1;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
ms(mp,0);ms(a,0);ms(b,0),ms(girl,0);ms(g,0);
for(int i=1;i<=k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
mp[x][y]=1;
}
int ans=0;
for(int i=1;i<=n;i++)
{
ms(used,0);
if(findx(i))ans++;
}
int imp=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j]==1)
{
mp[i][j]=0;
int tem=0;
ms(girl,0);
for(int u=1;u<=n;u++)
{
ms(used,0);
if(findx(u))tem++;
}
if(tem!=ans)imp++;
mp[i][j]=1;
}
}
}
printf("Board %d have %d important blanks for %d chessmen.\n",ce++,imp,ans);
}
}
5.Swap HDU - 2819(二分图匹配 巧用匹配数组)
题目思路
题目要把图变成对角线都为1的样子
很容易想到拿行和列进行二分图匹配
如果得到的答案不等于n
那么该图不能转变成对角线为1的样子
等于n 在做变换的操作
一开始我还在模拟
但写出来一直wa
看了下题解 发现题解是直接用匹配时记录的那个数组做交换
感觉好巧妙
后来还是wa了很多发 原因是vector没有初始化。。。
下次要注意一下
ac代码
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
using namespace std;
const int maxn = 1e3+10;
const int inf = 0x3f3f3f3f;
const ll llinf =0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
int n;
int mp[maxn][maxn],used[maxn],girl[maxn];
vector<int>a;
vector<int>b;
bool findx(int x)
{
for(int i=1;i<=n;i++)
{
//print1;
if(mp[x][i]==1)
{
if(used[i]==0)
{
used[i]=1;
if(girl[i]==0||findx(girl[i]))
{
girl[i]=x;//记录该行与哪一列匹配上了
return true;
}
}
}
}
return false;
}
int main()
{
while(~scanf("%d",&n))
{
a.clear();
b.clear();
ms(girl,0);ms(mp,0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&mp[i][j]);
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
ms(used,0);
if(findx(i))ans++;
}
if(ans!=n)printf("-1\n");
else
{
int cot=0;
for(int i=1;i<=n;i++)
{
while(girl[i]!=i)//直接对匹配数组进行操作 因为没有限制操作数所以不一定需要一次操作就满足条件
{
cot++;
int j=girl[i];
a.push_back(i);
b.push_back(j);
swap(girl[i],girl[j]);
}
}
printf("%d\n",cot);
for(int i=0;i<a.size();i++)
{
printf("C %d %d\n",a[i],b[i]);
}
}
}
}
6.Oil Skimming HDU - 4185(二分图匹配)
题目思路
一开始还是在按照之前的行和列匹配的思路想
怎么想都想不出这题怎么写
后来看了下题解说将相邻的点建边
直接对相邻的点做二分图匹配就好了
因为不知道哪些点在二分图的哪个部分
所以直接遍历全部 最后给答案除2就好
ac代码
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
using namespace std;
const int maxn = 1e3+10;
const int inf = 0x3f3f3f3f;
const ll llinf =0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
int n,cnt;
char mp[maxn][maxn];
int a[maxn][maxn],g[maxn][maxn],girl[maxn],used[maxn];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
bool findx(int x)
{
for(int i=1;i<=cnt;i++)
{
if(g[x][i]==1)
{
if(used[i]==0)
{
used[i]=1;
if(girl[i]==0||findx(girl[i]))
{
girl[i]=x;
return true;
}
}
}
}
return false;
}
int main()
{
int t,ce=1;
scanf("%d",&t);
while(t--)
{
ms(girl,0);ms(a,0);ms(g,0);
int n;cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",mp[i]+1);
for(int j=1;j<=n;j++)
{
if(mp[i][j]=='#')
a[i][j]=++cnt;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mp[i][j]=='#')
{
for(int u=0;u<4;u++)
{
int xx=i+dx[u];
int yy=j+dy[u];
if(mp[xx][yy]=='#')
{
g[a[i][j]][a[xx][yy]]=1;
}
}
}
}
}
int ans=0;
for(int i=1;i<=cnt;i++)
{
ms(used,0);
if(findx(i))ans++;
}
printf("Case %d: %d\n",ce++,ans/2);
}
}
后面的题慢慢写吧
本文地址:https://blog.csdn.net/daydreamer23333/article/details/107606341
下一篇: 害得我超囧冷人小夫妻