hdu2813One fihgt one(KM)

題目請戳這裡

題目大意：曹操帶了m個手下去打呂布，呂布有n個手下(n<=m)，現在他們決定用手下一對一單挑。給定k個單挑關系，表示呂布的手下VS曹操的手下獲得的傷害值，呂布的手下要全部打一次。現在要呂布為手下挑對手，使手下獲得的傷害值最小。

題目分析：就是要求一個最小權完備比對。KM算法解決之。注意建圖的時候邊權值取相反數，因為KM是求最大權比對的，求出最大權完備比對後再取反輸出。

關于KM算法，百科講的還不錯，不過還是有點抽象，要詳解的話推薦戳這裡

圖建好了就是跑模版的事了。

詳情請見代碼：

#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
using namespace std;

const int N = 205;
const int INF = 0x3f3f3f3f;
int n,m,k,lack;
int w[N][N];
int lx[N],ly[N];
bool sx[N],sy[N];
int match[N];

int dfs(int u)
{
    sx[u] = true;
    for(int v = 1;v <= m;v ++)
    {
        if(!sy[v])
        {
            int t = lx[u] + ly[v] - w[u][v];
            if(t == 0)
            {
                sy[v] = true;
                if(match[v] == -1 || dfs(match[v]))
                {
                    match[v] = u;
                    return 1;
                }
            }
            else
                if(lack > t)
                    lack = t;
        }
    }
    return 0;
}

void KM()
{
    int i;
    memset(match,-1,sizeof(match));
    for(i = 1;i <= n;i ++)
    {
        lx[i] = -INF;
        for(int j = 1;j <= m;j ++)
            if(lx[i] < w[i][j])
                lx[i] = w[i][j];
    }
    for(i = 1;i <= m;i ++)
        ly[i] = 0;
    for(int u = 1;u <= n;u ++)
    {
        while(1)
        {
            memset(sx,0,sizeof(sx));
            memset(sy,0,sizeof(sy));
            lack = INF;
            if(dfs(u))
                break;
            for(i = 1;i <= n;i ++)
                if(sx[i])
                    lx[i] -= lack;
            for(i = 1;i <= m;i ++)
                if(sy[i])
                    ly[i] += lack;
        }
    }
    int sum = 0;
    for(i = 1;i <= m;i ++)
        if(match[i] > -1)
            sum += w[match[i]][i];
    printf("%d\n",-sum);
}

int main()
{
    string s1,s2;
    int pl,pc;
    int i,j,injury;
    while(scanf("%d%d%d",&n,&m,&k) != EOF)
    {
        pc = pl = 1;
        map<string,int> lvbu,caocao;
        map<string,int>::iterator it;
        for(i = 1;i <= n;i ++)
            for(j = 1;j <= m;j ++)
                w[i][j] = -INF;
        while(k --)
        {
            cin>>s1>>s2;
            scanf("%d",&injury);
            it = lvbu.find(s1);
            if(it == lvbu.end())
            {
                lvbu[s1] = pl;
                i = pl ++;
            }
            else
                i = it->second;
            it = caocao.find(s2);
            if(it == caocao.end())
            {
                caocao[s2] = pc;
                j = pc ++;
            }
            else
                j = it->second;
            w[i][j] = -injury;
        }
        KM();
    }
    return 0;
}