hdu 1045 二分图最大匹配

深碍√TFBOYSˉ_ 2022-08-02 12:47 202阅读 0赞

建图的过程当时不会，参考了别人的代码

//hdu 1045
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    int g[20][20];
    int m1[20][20];
    int m2[20][20];
    int match[20];
    int flag;
    int vis[20];
    char maze[5][5];
    int p1,p2;
    void init(int n)
    {
    
        mem(match,-1);
        mem(vis,0);
        mem(g,0);
        mem(m1,0);    //??
        mem(m2,0);
    }
    bool dfs(int x)
    {
        for(int i=1;i<=p2;i++)
        {
            if(vis[i]!=flag && g[x][i])
            {
                vis[i]=flag;
    
                if(match[i]==-1 || dfs(match[i]))
                {
                    match[i] = x;
                    return 1;
                }
            }
        }
        return 0;
    }
    int solve()//二分图匹配
    {
        int ans=0;
        for(int i=1;i<=p1;i++)
        {
            flag=i;
            if(dfs(i))ans++;
        }
        return ans;
    }
    int main()
    {
        int n;
        while(~scanf("%d",&n) && n)
        {
            init(n);
            for(int i=0;i<n;i++)
            {
                scanf("%s",maze[i]);
            }
            //给行标号
            p1=0;
            int p=0;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    while(j<n && maze[i][j]=='X') m1[i+1][j+1]=-1,j++;
                    p++;
                    while(j<n && maze[i][j]!='X')
                    {
                        m1[i+1][j+1]=p;
                        j++;
                        if(p1<p)p1=p;
    
                    }
                }
            }
            //给列标号
            p2=0;
            p=0;
            for(int j=0;j<n;j++)
            {
                for(int i=0;i<n;i++)
                {
                    while(i<n && maze[i][j]=='X')m2[i+1][j+1]=-1,++i;
                    p++;
                    while(i<n && maze[i][j]!='X')
                    {
                        m2[i+1][j+1]=p;
                        i++;
                        if(p2<p)p2=p;
    
                    }
                }
            }
          //建图
          for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(m1[i][j]!=-1 && m2[i][j]!=-1)
                    {
                        g[m1[i][j]][m2[i][j]]=1;
                    }
                }
    
            }
            printf("%d\n",solve());
        }
        return 0;
    }