[kuangbin带你飞]专题10：匹配问题

骑猪看日落 2023-07-10 08:45 18阅读 0赞

# \[kuangbin带你飞\]专题10：匹配问题 #

### 文章目录 ###

*  \[kuangbin带你飞\]专题10：匹配问题
 *   *  1.Fire Net——HDU 1045
     *  2.The Accomodation of Students——HDU 2444
     *  3.Courses——HDU 1083
     *  4.棋盘游戏——HDU 1281
     *  5.Swap——HDU 2819
     *  6.Rain on your Parade——HDU 2389
     *  7.Oil Skimming——HDU 4185
     *  8.Antenna Placement——POJ 3020
     *  9.Strategic Game——HDU1054
     *  10.Air Raid——HDU 1151
     *  11.Treasure Exploration——POJ 2594
     *  12.Cat VS Dog——HDU 3829
     *  13.奔小康赚大钱——HDU 2255

--------------------

## 1.Fire Net——HDU 1045 ##

--------------------

[题目链接][Link 1]

**题意：**  
一个棋盘，其中某些区域是障碍物不能放东西，然后所放的物品必须满足不能在两者之前没有障碍物的情况下，位于同一行、或者同一列

**题解：**  
这题我并没有用建二分图，而是直接bfs

--------------------

## 2.The Accomodation of Students——HDU 2444 ##

--------------------

[题目链接][Link 2]

**题解：**  
首先判断判断是不是二分图，如果不是输出No  
如果是的话，再进行二分图匹配，直接套匈牙利算法即可，

但是tle了好几次，数组开小了。。。。

代码参考的这篇博客：  
[https://blog.csdn.net/u014422052/article/details/43604927?depth\_1-utm\_source=distribute.pc\_relevant.none-task&utm\_source=distribute.pc\_relevant.none-task][https_blog.csdn.net_u014422052_article_details_43604927_depth_1-utm_source_distribute.pc_relevant.none-task_utm_source_distribute.pc_relevant.none-task]

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=10010;
    int vis[maxn];
    struct Edge{
        
        int to,nxt;
    }edge[maxn];
    int n,m,tot;
    int head[maxn],color[maxn],linker[maxn];
    void init(){
        
        tot=0;
        memset(head,-1,sizeof(head));
    }
    void add(int u,int v){
        
        edge[tot].to=v;
        edge[tot].nxt=head[u];
        head[u]=tot++;
    }
    int bfs(){
        
        int s,now,cnt,v;
        memset(color,-1,sizeof(color));
        queue<int>q;
        q.push(1);
        color[1]=1;
        while(!q.empty()){
        
            s=q.front();
            q.pop();
            for(int i=head[s];i!=-1;i=edge[i].nxt){
        
                v=edge[i].to;
                if(color[v]==-1){
        
                    color[v]=1-color[s];
                    q.push(v);
                }
                else if(color[v]==color[s]){
        
                    return 1;
                }
            }
        }
        return 0;
    }
    int Find(int u){
        
        for(int j=head[u];j!=-1;j=edge[j].nxt){
        
            int v=edge[j].to;
            if(!vis[v]){
        
                vis[v]=1;
                if(linker[v]==-1||Find(linker[v])){
        
                    linker[v]=u;
                    return 1;
                }
            }
        }
        return 0;
    }
    int solve(){
        
        int ans=0;
        memset(linker,-1,sizeof(linker));
        for(int i=1;i<=n;i++){
        
            memset(vis,0,sizeof(vis));
            if(Find(i)){
        
                ans++;
            }
        }
        return ans;
    }
    int main(){
        
        while(~scanf("%d%d",&n,&m)){
        
            init();
            int u,v;
            for(int i=1;i<=m;i++){
        
                scanf("%d%d",&u,&v);
                add(u,v);
            }
            if(bfs()){
        
                printf("No\n");
                continue;
            }
            printf("%d\n",solve());
        }
        return 0;
    }

--------------------

## 3.Courses——HDU 1083 ##

--------------------

[题目链接][Link 3]

**题解：**  
课程看成二分图一部分、学生看成二分图另一部分。  
然后直接用匈牙利算法求最大匹配即可，  
如果最大匹配数=课程数，则：YES  
否则：NO

--------------------

## 4.棋盘游戏——HDU 1281 ##

--------------------

[题目链接][Link 4]

**题意：**  
n\*m的棋盘，其中只有k个位置可以放棋子。同一行或者同一列不能放“车”，题目其实有两问  
1.问最多可以放多少个棋子  
2.问在第1问的基础上，有多少个棋子的位置是不能改变的，如果改变第1问的结果就会改变

**题解：**  
针对这两个问题，分别来处理：  
1.直接用匈牙利算法求二分图的最大匹配即可  
2.对每个已经匹配的边，先删除，然后判断最大匹配数是不是相等，如果不相等则这个位置是不能变的，结果+1；最后输入结果即可

开始一直样例都过不了，原来是在后面判断边的时候，对匹配数组没有初始化。。。。。。

--------------------

## 5.Swap——HDU 2819 ##

--------------------

[题目链接][Link 5]

--------------------

## 6.Rain on your Parade——HDU 2389 ##

--------------------

[题目链接][Link 6]

**题解：**  
这题如果继续用匈牙利算法是肯定会tle的

于是采用**Hopcroft-Karp算法**，而且还必须用**邻接表**来存二分图

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=3010;
    struct node{
        
        int x,y,v;
    };
    node a[maxn],b[maxn];
    int vis[maxn],usedx[maxn],usedy[maxn];
    int n,m,tot;
    int dx[maxn],dy[maxn],depth,head[maxn];
    struct Edge{
        
        int v,nxt;
    }edge[maxn*maxn];
    void add(int u,int v){
        
        edge[tot].v=v;
        edge[tot].nxt=head[u];
        head[u]=tot++;
    }
    int Find(int u){
        
        for(int i=head[u];i!=-1;i=edge[i].nxt){
        
            int v=edge[i].v;
            if(vis[v]==0&&dx[u]==dy[v]-1){
        
                vis[v]=1;
                if(!usedy[v]||Find(usedy[v])){
        
                    usedy[v]=u;
                    usedx[u]=v;
                    return 1;
                }
            }
        }
        return 0;
    }
    bool bfs(){
        
        queue<int>q;
        depth=inf;
        memset(dx,-1,sizeof(dx));
        memset(dy,-1,sizeof(dy));
        for(int i=1;i<=n;i++){
        
            if(!usedx[i]){
        
                dx[i]=0;
                q.push(i);
            }
        }
        while(!q.empty()){
        
            int u=q.front();
            q.pop();
            if(depth<dx[u]){
        
                break;
            }
            for(int j=head[u];j!=-1;j=edge[j].nxt){
        
                int v=edge[j].v;
                if(dy[v]==-1){
        
                    dy[v]=dx[u]+1;
                    if(!usedy[v]){
        
                        depth=dy[v];
                    }
                    else{
        
                        dx[usedy[v]]=dy[v]+1;
                        q.push(usedy[v]);
                    }
                }
            }
        }
        if(depth==inf){
        
            return 0;
        }
        return 1;
    }
    void init(){
        
        memset(head,-1,sizeof(head));
        tot=0;
    }
    int main(){
        
        int cas;
        int t,x,y;
        scanf("%d",&cas);
        for(int k=1;k<=cas;k++){
        
            init();
            scanf("%d%d",&t,&n);
            for(int i=1;i<=n;i++){
        
                scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
            }
            scanf("%d",&m);
            for(int i=1;i<=m;i++){
        
                scanf("%d%d",&x,&y);
                for(int j=1;j<=n;j++){
        
                    int d=(a[j].x-x)*(a[j].x-x)+(a[j].y-y)*(a[j].y-y);
                    if(d<=a[j].v*t*a[j].v*t){
        
                        add(j,i);
                    }
                }
            }
            int ans=0;
            memset(usedx,0,sizeof(usedx));
            memset(usedy,0,sizeof(usedy));
            while(bfs()){
        
                memset(vis,0,sizeof(vis));
                for(int i=1;i<=n;i++){
        
                    if(!usedx[i]&&Find(i)){
        
                        ans++;
                    }
                }
            }
            printf("Scenario #%d:\n",k);
            printf("%d\n\n",ans);
        }
        return 0;
    }

--------------------

## 7.Oil Skimming——HDU 4185 ##

--------------------

[题目链接][Link 7]

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=610;
    char mp[maxn][maxn];
    int g[maxn][maxn];
    int relate[maxn][maxn];
    int match[maxn],vis[maxn];
    int t,n;
    int temp;
    int Find(int u){
        
        for(int v=0;v<temp;v++){
        
            if(vis[v]==0&&g[u][v]){
        
                vis[v]=1;
                if(match[v]==0||Find(match[v])){
        
                    match[v]=u;
                    return 1;
                }
            }
        }
        return 0;
    }
    int solve(){
        
        int ans=0;
        memset(match,0,sizeof(match));
        for(int i=0;i<temp;i++){
        
            memset(vis,0,sizeof(vis));
            if(Find(i)){
        
                ans++;
            }
        }
        return ans;
    }
    int main(){
        
        scanf("%d",&t);
        int cas=1;
        while(t--){
        
            scanf("%d",&n);
            getchar();
            memset(relate,0,sizeof(relate));
            memset(g,0,sizeof(g));
            temp=0;
            for(int i=0;i<n;i++){
        
                scanf("%s",mp[i]);
                getchar();
                for(int j=0;j<n;j++){
        
                    if(mp[i][j]=='#'){
        
                        relate[i][j]=temp++;
                    }
                }
            }
            for(int i=0;i<n;i++){
        
                for(int j=0;j<n;j++){
        
                    if(mp[i][j]!='#')
                        continue;
                    if(mp[i-1][j]=='#'){
        
                        g[relate[i][j]][relate[i-1][j]]=1;
                    }
                    if(mp[i+1][j]=='#'){
        
                        g[relate[i][j]][relate[i+1][j]]=1;
                    }
                    if(mp[i][j-1]=='#'){
        
                        g[relate[i][j]][relate[i][j-1]]=1;
                    }
                    if(mp[i][j+1]=='#'){
        
                        g[relate[i][j]][relate[i][j+1]]=1;
                    }
                }
            }
            int ans=solve();
            printf("Case %d: %d\n",cas++,ans/2);
        }
        return 0;
    }

--------------------

## 8.Antenna Placement——POJ 3020 ##

--------------------

[题目链接][Link 8]

**题解：**

最少路径点覆盖=原图点个数-新图最大匹配数

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=50;
    const int maxm=15;
    const int maxnum=maxn*maxm;
    int mp[maxnum][maxnum];
    int vis[maxnum];
    int match[maxnum],newG[maxn][maxm];
    char G[maxn][maxm];
    int n,m,cnt;
    int Find(int i){
        
        for(int j=1;j<=cnt;j++){
        
            if(vis[j]==0&&mp[i][j]){
        
                vis[j]=1;
                if(match[j]==0||Find(match[j])){
        
                    match[j]=i;
                    return 1;
                }
            }
        }
        return 0;
    }
    int solve(){
        
        int num=0;
        memset(match,0,sizeof(match));
        for(int i=1;i<=cnt;i++){
        
            memset(vis,0,sizeof(vis));
            if(Find(i)){
        
                num++;
            }
        }
        return num;
    }
    int  main(){
        
        int t;
        scanf("%d",&t);
        while(t--){
        
            cnt=0;
            memset(mp,0,sizeof(mp));
            memset(newG,0,sizeof(newG));
            scanf("%d%d",&n,&m);
            for(int i=0;i<n;i++){
        
                scanf("%s",G[i]);
            }
            for(int i=0;i<n;i++){
        
                for(int j=0;j<m;j++){
        
                    if(G[i][j]=='*'){
        
                        cnt++;
                        newG[i][j]=cnt;
                    }
                }
            }
            for(int i=0;i<n;i++){
        
                for(int j=0;j<m;j++){
        
                    if(newG[i][j]>0){
        
                        if(i!=0){
        
                            if(newG[i-1][j]>0){
        
                                mp[newG[i][j]][newG[i-1][j]]=1;
                            }
                        }
                        if(i!=n-1){
        
                            if(newG[i+1][j]>0)
                                mp[newG[i][j]][newG[i+1][j]]=1;
                        }
                        if(j!=0){
        
                            if(newG[i][j-1]>0){
        
                                mp[newG[i][j]][newG[i][j-1]]=1;
                            }
                        }
                        if(j!=m-1){
        
                            if(newG[i][j+1]>0)
                                mp[newG[i][j]][newG[i][j+1]]=1;
                        }
                    }
                }
            }
            printf("%d\n",cnt-solve()/2);
        }
        return 0;
    }

--------------------

## 9.Strategic Game——HDU1054 ##

--------------------

[题目链接][Link 9]

**题解：**

最小点覆盖=最大匹配数

这题通过题目所给，发现用邻接表建二分图要方便很多，求最大匹配数直接用匈牙利算法即可

--------------------

## 10.Air Raid——HDU 1151 ##

--------------------

[题目链接][Link 10]

**题解：**

看题就知道又是一道非常经典的二分图匹配问题，发现数据不大，匈牙利算法可以过，于是先把最大匹配数给求出来，与答案一比，发现：答案=顶点个数-最大匹配数

其实题目是求最小路径覆盖；  
**最小路径覆盖=顶点个数-最大匹配数**

--------------------

## 11.Treasure Exploration——POJ 2594 ##

--------------------

[题目链接][Link 11]

**题解：**  
开始没怎么看题目，以为就是简单的最小路径覆盖，但是一交wa了，后面也是参考的别人的题解，原来是**点可以重复**（好吧，原谅我英文不好），然后利用图论中的**Floyd算法求传递闭包**（只能说绝了，我是真的没想到，感觉离散也是白学了。。。）  
然后用匈牙利算法求一下最小路径覆盖即可

--------------------

## 12.Cat VS Dog——HDU 3829 ##

--------------------

[题目链接][Link 12]

**题解：**  
乍一看，觉得就是最大独立集，但是一直没有找到突破口。  
我们可以存储每个孩子喜欢的动物和不喜欢的动物，只有A喜欢的动物恰好是B不喜欢的动物时，建边，这就是建立二分图的过程

但是需要注意的是：只有一群孩子，而我们要建立二分图，也就相当于每个孩子既在左边又在右边（即：**匹配了两次，最终结果需要除2**）

最后：最大独立集=点数-最大匹配数（用匈牙利算法即可）

--------------------

## 13.奔小康赚大钱——HDU 2255 ##

--------------------

[题目链接][Link 13]

**题解：**  
带权的二分图最大匹配，KM算法

另写了一篇博客：  
[HDU 2255：奔小康赚大钱（带权二分图最大匹配-KM算法）][HDU 2255_-KM]

[Link 1]: https://vjudge.net/problem/HDU-1045
[Link 2]: https://vjudge.net/problem/HDU-2444
[https_blog.csdn.net_u014422052_article_details_43604927_depth_1-utm_source_distribute.pc_relevant.none-task_utm_source_distribute.pc_relevant.none-task]: https://blog.csdn.net/u014422052/article/details/43604927?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
[Link 3]: https://vjudge.net/problem/HDU-1083
[Link 4]: https://vjudge.net/problem/HDU-1281
[Link 5]: https://vjudge.net/problem/HDU-2819
[Link 6]: https://vjudge.net/problem/HDU-2389
[Link 7]: https://vjudge.net/problem/HDU-4185
[Link 8]: https://vjudge.net/problem/POJ-3020
[Link 9]: https://vjudge.net/problem/HDU-1054
[Link 10]: https://vjudge.net/problem/HDU-1151
[Link 11]: https://vjudge.net/problem/POJ-2594
[Link 12]: https://vjudge.net/problem/HDU-3829
[Link 13]: https://vjudge.net/problem/HDU-2255
[HDU 2255_-KM]: https://blog.csdn.net/boliu147258/article/details/104663349