首页 > 其他 > 详细

Kuangbin带你飞 专题十 匹配问题

时间:2020-03-30 15:30:07      阅读:74      评论:0      收藏:0      [点我收藏+]

HDU1045 Fire Net

思路:

将每行中每列中被障碍物分割的区域分别进行缩点成为不同的点

将横坐标分成一组,纵坐标分成一组进行二分图最大匹配

 

技术分享图片
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
 using namespace std;
 const int maxn=100;
 char s[maxn][maxn];
 int idx[maxn][maxn],idy[maxn][maxn],matching[maxn],check[maxn];
 int n,cntx,cnty;
 vector<int> a[maxn];
bool dfs(int u)
{
    for (int i=0;i<a[u].size();i++){
        int v = a[u][i];
        if (!check[v]) {
            check[v] = true;
            if (matching[v]==-1||dfs(matching[v])) {
                matching[v]=u;
                matching[u]=v;
                return true;
            }
        }
    }
    return false;
}
int hungarian(int cntx)
{
    int ans=0;
    memset(matching,-1,sizeof(matching));
    for (int u=0;u<=cntx;++u){
        if(matching[u]==-1){
            memset(check, 0, sizeof(check));
            if(dfs(u))
                ++ans;
        }
    }
    return ans;
}
void init()
{
    memset(idx,0,sizeof(idx));
     memset(idy,0,sizeof(idy));
     memset(s,0,sizeof(s));
     memset(matching,0,sizeof(matching));
     for(int i=0;i<maxn;i++) a[i].clear();
    cntx=cnty=0;
}
 int main()
 {
     while(scanf("%d",&n)&&n){
         init();
         for(int i=0;i<n;i++) scanf("%s",s[i]);
         for(int i=0;i<n;i++){
             for(int j=0;j<n;j++){
                 if(s[i][j]==.) idx[i][j]=cntx;
                else if(s[i][j]==X&&s[i][j+1]!=X) cntx++;
             }
            if(s[i][n-1]!=X&&s[i+1][0]!=X&&i!=n-1) cntx++;
            for(int j=0;j<n;j++){
                if(s[j][i]==.) idy[j][i]=cnty;
                else if(s[j][i]==X&&s[j+1][i]!=X) cnty++;
            }
            if(s[n-1][i]!=X&&s[0][i+1]!=X&&i!=n-1) cnty++;
         }
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                if(s[i][j]!=X)
                    a[idx[i][j]].push_back(idy[i][j]+cntx+1);
        cout<<hungarian(cntx)<<endl;
     }
    return 0;
 }
View Code

 

HDU 2444 The Accomodation of Students

思路:

先用染色法判断是否为二分图,并且将点分组

如果为二分图,就进行最大匹配

 

技术分享图片
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
 using namespace std;
 const int maxn=205;
 vector<int> a[maxn],l;
 int color[maxn],matching[maxn],check[maxn],vis[maxn];
 int n,m,u,v;
 void init()
 {
     memset(matching,-1,sizeof(matching));
     memset(color,-1,sizeof(color));
     memset(vis,0,sizeof(vis));
     for(int i=0;i<maxn;i++) a[i].clear();
     l.clear();
 }
 bool judge()
 {
     color[1]=0;
     queue<int> q;
     q.push(1);
     vis[1]=1;
     while(!q.empty()){
         int u=q.front();
         if(color[u]==0) l.push_back(u);
         q.pop();
         for(int i=0;i<a[u].size();i++){
             int v=a[u][i];
             if(vis[v]){
                 if(color[u]==color[v]) return false;
                 else continue;
             }
            else{
                vis[v]=1;
                color[v]=color[u]^1;
                q.push(v);
            }
         }
     }
    return true;
 }
 bool dfs(int u)
{
    for (int i=0;i<a[u].size();++i){
        int v=a[u][i];
        if (!check[v]){  
            check[v]=true;
            if (matching[v]==-1||dfs(matching[v])){
                matching[v]=u;
                matching[u]=v;
                return true;
            }
        }
    }
    return false; 
}
int hungarian()
{
    int ans=0;
    memset(matching,-1,sizeof(matching));
    for(int u=1;u<=n;++u) {
        if(matching[u]==-1) {
            memset(check,0,sizeof(check));
            if (dfs(u))
                ++ans;
        }
    }
    return ans;
}
 int main()
 {
     while(scanf("%d%d",&n,&m)!=EOF){
         init();
         for(int i=1;i<=m;i++){
             scanf("%d%d",&u,&v);
             a[u].push_back(v);
             a[v].push_back(u);
         }
        if(!judge()) cout<<"No"<<endl;
        else cout<<hungarian()<<endl;
     }
    return 0;
  } 
View Code

 

HDU 1083 Courses

思路:

裸题,直接进行匹配就好了

 

技术分享图片
#include<iostream>
#include<algorithm>
#include<vector> 
#include<cstring>
 using namespace std;
 const int maxn=405;
 vector<int> a[maxn];
 int matching[maxn],check[maxn];
 int n,m,t,cnt,u,v;
 bool dfs(int u)
 {
     for(int i=0;i<a[u].size();i++){
         int v=a[u][i];
         if(!check[v]){
             check[v]=true;
             if(matching[v]==-1||dfs(matching[v])){
                 matching[u]=v;
                 matching[v]=u;
                 return true;
             }
         }
     }
    return false;
 }
 int hungarian()
 {
     int ans=0;
     memset(matching,-1,sizeof(matching));
     for(int i=1;i<=n;i++){
         if(matching[i]==-1){
             memset(check,0,sizeof(check));
             if(dfs(i)) ans++;
         }
     }
    return ans;
 }
 int main()
 {
     scanf("%d",&t);
     while(t--){
         scanf("%d%d",&n,&m);
        for(int i=0;i<=n+m;i++) a[i].clear(); 
         for(int i=1;i<=n;i++){
             scanf("%d",&cnt);
             while(cnt--){
                 scanf("%d",&u);
                 a[i].push_back(u+n);
                 a[u+n].push_back(i);
             }
         }
         if(hungarian()==n) cout<<"YES"<<endl;
         else cout<<"NO"<<endl;
     }
    return 0;
  } 
View Code

 

HDU 1281 棋盘游戏

思路:

先进行二分图匹配求出最大匹配数

然后将每个可行点从棋盘中移去看看最大匹配数是否会减少

(邻接矩阵跟邻接表的板子略有不同。。被卡了好久)

 

技术分享图片
#include<iostream>
#include<algorithm>
#include<cstring> 
 using namespace std;
 const int maxn=105;
 int matching[maxn],check[maxn],s[2*maxn][2*maxn];
 int n,m,Cas=1,k,u,v,ans1,ans2;
 void init()
 {
     memset(s,0,sizeof(s));
     ans1=ans2=0;
 }
 bool dfs(int u)
 {
     for(int i=1;i<=m;i++){
         if(s[u][i]){
             if(!check[i]){
                 check[i]=true;
                 if(matching[i]==-1||dfs(matching[i])){
                     //matching[u]=i;
                     matching[i]=u;
                     return true;
                 }
             }
         }
     }
     return false;
 }
 int hungarian()
 {
     int ans=0;
     memset(matching,-1,sizeof(matching));
     for(int i=1;i<=n;i++){
         memset(check,0,sizeof(check));
         if(dfs(i)) ans++;
     }
    return ans;
 }
 int main()
 {
     while(scanf("%d%d%d",&n,&m,&k)!=EOF){
         init();
         for(int i=1;i<=k;i++){
             scanf("%d%d",&u,&v);
             s[u][v]=1;
         }
        ans2=hungarian();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s[i][j]){
                    s[i][j]=0;
                    if(hungarian()<ans2) ans1++;
                    s[i][j]=1;
                }
            }
        }
        printf("Board %d have %d important blanks for %d chessmen.\n",Cas++,ans1,ans2);
     }
     return 0;
  } 
View Code

 

Kuangbin带你飞 专题十 匹配问题

原文:https://www.cnblogs.com/overrate-wsj/p/12598164.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!