bzoj2150: 部落战争

喜欢ヅ旅行 2021-09-29 16:48 213阅读 0赞

补了一下匈牙利的各种骚操作。

最大匹配等于最小覆盖

最大独立集=n-最小覆盖

最大团=补图的最大独立集

对于这题，把每个点拆成两个，可以到达的就连边。

我匈牙利的模版是真不熟。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cstdlib>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int dx[4]={
        1,1,1,1};
    int dy[4]={
        1,-1,1,-1};
    
    struct node
    {
        int x,y,next;
    }a[210000];int len,last[3100];
    void ins(int x,int y)
    {
        len++;
        a[len].x=x;a[len].y=y;
        a[len].next=last[x];last[x]=len;
    }
    
    int match[3100];
    bool chw[3100];
    bool find_muniu(int x)
    {
        for(int k=last[x];k;k=a[k].next)
        {
            int y=a[k].y;
            if(chw[y]==true)
            {
                chw[y]=false;
                if(match[y]==0||find_muniu(match[y])==true)
                {
                    match[y]=x;
                    return true;
                }
            }
        }
        return false;
    }
    
    int nm,num[110][110];
    char ss[110][110];
    int main()
    {
        int n,m,R,C;
        scanf("%d%d%d%d",&n,&m,&R,&C);
        for(int i=0;i<=1;i++)
        {
            dx[i]*=R,dy[i]*=C;
            dx[i+2]*=C,dy[i+2]*=R;
        }
        nm=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",ss[i]+1);
            for(int j=1;j<=m;j++)
                if(ss[i][j]=='.')num[i][j]=++nm;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(ss[i][j]=='.')
                    for(int t=0;t<=3;t++)
                    {
                        int ti=i+dx[t],tj=j+dy[t];
                        if(ti>0&&ti<=n&&tj>0&&tj<=m&&ss[ti][tj]=='.')
                            ins(num[i][j],num[ti][tj]);
                    }
                
        int ans=0;
        memset(match,0,sizeof(match));
        for(int i=1;i<=nm;i++)
        {
            memset(chw,true,sizeof(chw));
            if(find_muniu(i)==true)ans++;
        }
        printf("%d\n",nm-ans);
        return 0;
    }

转载于:https://www.cnblogs.com/AKCqhzdy/p/8628286.html