KM模板

KM模板

HDU2255

老是听说费用流被稠密图卡

没找到\(N^3\)的讲解，只学了个\(N^4\)的dfs，不敢交UOJ..

Code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define yuucute 1
using std::min;
using std::max;
const int N=302;
int va[N],vb[N],la[N],lb[N],w[N][N],mat[N],mi,n;
bool dfs(int now)
{
    va[now]=1;
    for(int i=1;i<=n;i++)
        if(!vb[i])
        {
            if(w[now][i]==la[now]+lb[i])
            {
                vb[i]=1;
                if(!mat[i]||dfs(mat[i]))
                    return mat[i]=now,true;
            }
            else mi=min(mi,la[now]+lb[i]-w[now][i]);
        }
    return false;
}
void work()
{
    memset(mat,0,sizeof mat);
    for(int i=1;i<=n;i++)
    {
        la[i]=-(1<<30);
        lb[i]=0;
        for(int j=1;j<=n;j++)
            scanf("%d",&w[i][j]),la[i]=max(la[i],w[i][j]);
    }
    for(int i=1;i<=n;i++)
    {
        while(yuucute)
        {
            memset(va,0,sizeof va);
            memset(vb,0,sizeof vb);
            mi=1<<30;
            if(dfs(i)) break;
            for(int j=1;j<=n;j++)
            {
                if(va[j]) la[j]-=mi;
                if(vb[j]) lb[j]+=mi;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans+=w[mat[i]][i];
    printf("%d\n",ans);
}
int main()
{
    while(scanf("%d",&n)!=EOF) work();
    return 0;
}

---

2019.2.19