hdu2255 KM算法入门 KM算法模板

旧城等待， 2022-08-02 15:40 147阅读 0赞

好难啊~~

//KM算法模板（参考别人代码）
    //还不怎么理解 存下来以后慢慢懂
    #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;
    }
    
    const int N=303;
    
    int g[N][N];
    int lx[N];int ly[N];
    int slack[N];
    int match[N];
    int visx[N];int visy[N];
    
    int n;
    bool dfs(int x)
    {
        visx[x]=1;            
        for(int i=1;i<=n;i++)
        {
            if(visy[i])continue;        
            int t=lx[x]+ly[i]-g[x][i];
            if(t==0)
            {
                visy[i]=1;                        //只有当t==0的时候标记为访问过
                if(match[i]==-1 || dfs(match[i]))
                {
                    match[i]=x;
                    return 1;
                }
            }
            else if(slack[i]>t)slack[i]=t;
        }
        return 0;
    }
    
    int KM()
    {
        mem(match,-1);
        mem(ly,0);              //ly内容全部设置为最小
        for(int i=1;i<=n;i++)  //这步操作是把lx内容全部设置为最大
        {
            lx[i]=-inf;
            for(int j=1;j<=n;j++)
            {
                lx[i]=max(lx[i],g[i][j]);
            }
    
        }
        for(int j=1;j<=n;j++)
        {
            mem(slack,inf);
            while(1)
            {
                mem(visx,0);      
                mem(visy,0);
                if(dfs(j))break;  //找到增广轨就退出
                int d=inf;
                for(int i=1;i<=n;i++)
                {
                    if(!visy[i] && slack[i]<d) d=slack[i];//减去的数要为slack中最小的
                }
                for(int i=1;i<=n;i++)
                {
                    if(visx[i])lx[i]-=d;    //visx中访问过的就减去d
                }
                for(int i=1;i<=n;i++)
                {
                    if(visy[i])ly[i]+=d;       //visy中访问过的就加上d
                    else slack[i]-=d;          //没访问过的slack[i]要减去d
                }
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)         //最后统计答案
        {
            if(match[i]!=-1)ans+=g[match[i]][i];
        }
        return ans;
    }
    
    int main()
    {
    
        while(~scanf("%d",&n))
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    g[i][j]=in();
                }
    
            }
            printf("%d\n",KM());
        }
        return 0;
    }