当前位置：移动技术网 > 移动技术>移动开发>IOS > kuangbin专题十匹配问题

kuangbin专题十匹配问题

2020年07月28日 | 移动技术网移动技术 | 我要评论

把最近刷的匹配问题全部放这里算了
应该不会把这个专题刷完
大概率写着写着就鸽了

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

您可能感兴趣的文章:

如对本文有疑问，点击进行留言回复！！

牛客编程巅峰赛S1第6场 - 黄金&钻石&王者题解

牛牛爱奇数链接：https://ac.nowcoder.com/acm/contest/6629/A来源：牛客网... [阅读全文]
2020牛客多校第六场（H-Harmony Pairs）

题目地址题意：给出nnn，然后求出从000到nnn有多少个数对，满足第一个数小于第二个数，但是第一个数的各位之... [阅读全文]
阿里秋招 7月24日笔试题回顾（吃烧饼开关灯）

阿里秋招 7月24日笔试题回顾题目一吃烧饼题目一开关灯题目一吃烧饼解题思路：dp问题，当前的饼数不能... [阅读全文]
纵横字谜的答案 Crossword Answers, ACM/ICPC World Finals 1994, UVa232

#include <iostream>#include <algorithm>#incl... [阅读全文]
HDU - 5880 Family View (AC自动机修改母串)

Family View (AC自动机修改母串)题目大意：给出一些敏感词，如果在文章中出现的话，用 ‘ * ’ 替... [阅读全文]
HDU - 2082 生成函数基础题

这些题都可以暴力直接做，但用于练习生成函数。（虽然并没有。。。马上做几道难题练练）#include<ios... [阅读全文]
HDU1085 —— 生成函数入门题

(1+X^i)*……最经典的生成函数。#include<iostream>#include<c... [阅读全文]
[HDU-1398] 生成函数基础题

还是经典生成函数：(1+x^i)#include<iostream>#include<cstr... [阅读全文]
iOS14Beta3续航怎么样 iOS14Beta3续航能力介绍

ios 14 第三个测试版本发布已经快一周，该版本更新的内容相对上一个版本来说较多，同时解决了升级后内存被严重占用的 bug。在一周的使用过程中，续航并没有较大... [阅读全文]
iOS14Beta3稳定性怎么样 iOS14Beta3升级建议介绍

每年wwdc全球开发者大会结束后，苹果就会放出beta版的ios、macos、ipados等，今年的ios 14也不例外。截止到7 月 24 日，苹果已经正式发... [阅读全文]

网友评论


验证码：

kuangbin专题十 匹配问题

2020年07月28日 | 移动技术网移动技术 | 我要评论

1.Fire Net HDU - 1045 （二分图匹配 匈牙利算法）

题目思路

ac代码

2.The Accomodation of Students HDU - 2444 （交叉染色法 二分图匹配）

题目思路

ac代码

3.Courses HDU - 1083（二分图匹配 匈牙利算法）

题目思路

ac代码

4.棋盘游戏 HDU - 1281（二分图匹配 删边找重要点）

题目思路

ac代码

5.Swap HDU - 2819（二分图匹配 巧用匹配数组）

题目思路

ac代码

6.Oil Skimming HDU - 4185（二分图匹配）

题目思路

ac代码

您可能感兴趣的文章:

相关文章:

网友评论

kuangbin专题十匹配问题

1.Fire Net HDU - 1045 （二分图匹配匈牙利算法）

2.The Accomodation of Students HDU - 2444 （交叉染色法二分图匹配）

3.Courses HDU - 1083（二分图匹配匈牙利算法）

4.棋盘游戏 HDU - 1281（二分图匹配删边找重要点）

5.Swap HDU - 2819（二分图匹配巧用匹配数组）