最大匹配

HDU 1045 Fire Net

Posted on

忍不住再水一道 这是我第一次完全是自己转化出来的二分匹配题 先说好代码丑 臭 长 想看简介的还是点下标签的 叉叉 吧
但毕竟是自己的亲儿子 蛤蛤

因为这题的矩阵范围是4*4 特别小 暴搜也是随便过的 这里我就不贴了 和之前写的一道超暴力回溯差不多 但是简单的很多

还是讲讲二分的吧 如果是平时一对一的匹配 只要 把行看成一个集合 把列看成一个集合进行匹配即可 但这里一行可以与多列匹配 一列与多行匹配 需要重新建图

我的烂思路就是再开两个矩阵 一个记录新的 行 一个记录新的列 再建立方向矩阵 套模板即可

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
int n,nrow,ncol;
const int maxn=16;
bool g[maxn][maxn],vis[maxn];
char mat[maxn][maxn];
int row[maxn][maxn],col[maxn][maxn],link[maxn];
int hungary();
int dfs(int x);

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        getchar();
        for(int i=1; i<=n; i++) scanf("%s",mat[i]+1);
        int num=1,flag[3];
        for(int i=1; i<=n; i++)//建立行矩阵
        {
            flag[0]=flag[1]=flag[2]=0;
            for(int j=1; j<=n; j++)
                if(mat[i][j]=='X')
                {
                    row[i][j]=0;
                    flag[1]=j;
                }
                else
                {
                    if(flag[0]&&flag[1]&&flag[0]<flag[1])//如果同时存在.和X  并且  .  在X 前面
                    {
                        row[i][j]=n+num;
                        flag[2]=1;
                    }
                    else row[i][j]=i;
                    if(!flag[0]) flag[0]=j;
                }
            if(flag[2]) num++;
        }
        nrow=n+num-1;//新行长度

        num=1;
        for(int i=1; i<=n; i++)//建立新列 与上相同
        {
            flag[0]=flag[1]=flag[2]=0;
            for(int j=1; j<=n; j++)
                if(mat[j][i]=='X')
                {
                    col[j][i]=0;
                    flag[1]=j;
                }
                else
                {
                    if(flag[0]&&flag[1]&&flag[0]<flag[1])
                    {
                        col[j][i]=n+num;
                        flag[2]=1;
                    }
                    else col[j][i]=i;
                    if(!flag[0]) flag[0]=j;
                }
            if(flag[2]) num++;
        }
        ncol=n+num-1;

        memset(g,false,sizeof g);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                g[row[i][j]][col[i][j]]=true;//建立邻接矩阵
        g[0][0]=false;
        int ans=hungary();//套模板
        printf("%d\n",ans);
    }
    return 0;
}

int hungary()
{
    int num=0;
    memset(link,-1,sizeof link);
    for(int i=1;i<=nrow;i++)
    {
        memset(vis,false,sizeof vis);
        num+=dfs(i);
    }
    return num;
}

int dfs(int x)
{
    for(int i=1;i<=ncol;i++)
        if(!vis[i]&&g[x][i])
        {
            vis[i]=true;
            if(link[i]==-1||dfs(link[i]))
            {
                link[i]=x;
                return 1;
            }
        }
    return 0;
}
最大匹配

HDU 1498 50 years, 50 colors

Posted on

尽管是大水题 但是再怎么说就是自己走过的路啊
不过现在只是二分图入门阶段 到现在为止接触的一些题目真的是太水了 只要 吧题目理解 套个模板就好了 所以这里就只拿一个hdu1498作为水题典例

简单说 题目是个最小点覆盖问题 二分图的最小点覆盖==最大匹配数 问的是哪些数字在k步操作内无法完全覆盖 也就是说最大匹配大于k的有哪些

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <iterator>

using namespace std;
const int maxn=105;
int n,k;
int g[maxn][maxn],link[maxn];
bool vis[maxn];
set<int> kao;
int hungary(int);
bool dfs(int,int);

int main()
{
    int temp,ans[maxn];
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        if(n==0&&k==0) break;
        kao.clear();
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
            {
                scanf("%d",&temp);
                kao.insert(temp);
                g[i][j]=temp;
            }
        int num=0,kase=0;
        for(set<int>::iterator it=kao.begin(); it!=kao.end(); it++)
        {
            temp=hungary(*it);
            if(temp>k) ans[num++]=*it;
        }
        if(num==0) printf("-1");
        else
        {
            sort(ans,ans+num);
            for(int i=0; i<num; i++)
            {
                if(kase++) putchar(' ');
                printf("%d",ans[i]);
            }
        }
        puts("");
    }
    return 0;
}
int hungary(int key)
{
    int num=0;
    for(int i=1; i<=n; i++) link[i]=-1;
    memset(link,-1,sizeof link);
    for(int i=1; i<=n; i++)
    {
        memset(vis,false,sizeof vis);
        if(dfs(i,key)) num++;
    }
    return num;
}

bool dfs(int x,int key)
{
    for(int i=1; i<=n; i++)
        if(!vis[i]&&g[x][i]==key)
        {
            vis[i]=true;
            if(link[i]==-1||dfs(link[i],key))
            {
                link[i]=x;
                return true;
            }
        }
    return false;
}
最大匹配

FZU 2039 Pets

Posted on

匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。

其实说白了 这个算法用途有限 只能求二分图的最大匹配(如果没有任何扩展,毕竟我是鶸……

题目是一个人与狗的故事
这里每个人都想日狗 所以肯定是一对一的啊 但总共有 n个人 m只狗 e个先决条件
这些条件中 第ai个人不喜欢第bi只狗
问最多能让多少人 日到狗

AC Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <cmath>
#include <iostream>
#include <cstdlib>

using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1100;
int n,m,qnum;
int cus[maxn];
bool vis[maxn],g[maxn][maxn];

void init()
{
    memset(g,true,sizeof g);
    memset(cus,0,sizeof cus);
    int u,v;
    for(int i=0; i<qnum; i++)
    {
        scanf("%d%d",&u,&v);
        g[u][v]=false;
    }
}

bool fin(int a)
{
    for(int i=1; i<=m; i++)
        if(g[a][i]&&!vis[i])
        {
            vis[i]=true;
            if(cus[i]==0||fin(cus[i]))
            {
                cus[i]=a;
                return true;
            }
        }
    return false;
}

int main()
{
    int test;
    scanf("%d",&test);
    for(int t=1; t<=test; t++)
    {
        scanf("%d%d%d",&n,&m,&qnum);
        init();
        int ans=0;
        for(int i=1; i<=n; i++)
        {
            memset(vis,false,sizeof vis);
            if(fin(i)) ans++;
        }
        printf("Case %d: %d\n",t,ans);
    }
    return 0;
}