kuangbin专题十 匹配问题
程序员文章站
2022-04-23 13:46:26
把最近刷的匹配问题全部放这里算了应该不会吧这个专题刷完大概率写着写着就鸽了1.Fire Net HDU - 1045 （二分图匹配 匈牙利算法）题目思路二分图匹配的简单题 第一次做没懂怎么建图看了下题解 发现是对行和列进行缩点然后对行和列重合的数字建边再跑匈牙利算法 求值ac代码#include #include #include #include #in...
把最近刷的匹配问题全部放这里算了
应该不会把这个专题刷完
大概率写着写着就鸽了
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