二分图最大权匹配（搭个板子，粘俩题）

先讲二分图最大权匹配做了什么：

先说一说人尽皆知csl匈牙利最大匹配做的事是二分图两边点的最大匹配，但如果边权有值咋整呢，这就用到了二分图最大权匹配，让你可以匹配过后获得最大的权值。

沾板子（kuangbin好菜牛逼）

int g[maxn][maxn], linker[maxn], lx[maxn], ly[maxn];
int slack[maxn], nx, ny, t, n, m;
bool visx[maxn], visy[maxn];
bool dfs(int x)
{
    visx[x] = 1;
    for(int y = 0; y < ny; y++){
        if(visy[y]) continue;
        int tmp = lx[x] + ly[y] - g[x][y];
        if(tmp == 0){
            visy[y] = 1;
            if(linker[y] == -1 || dfs(linker[y])){
                linker[y] = x;
                return 1;
            }
        }
        else if(slack[y] > tmp) slack[y] = tmp;
    }
    return false;
}

int KM()
{
    memset(linker, -1, sizeof(linker));
    memset(ly, 0, sizeof(ly));
    for(int i = 0; i < nx; i++)
    {
        lx[i] = -INF;
        for(int j = 0; j < ny; j++)
            if(g[i][j] > lx[i]) lx[i] = g[i][j];
    }
    for(int x = 0; x < nx; x++){
        for(int i = 0; i < ny; i++)
            slack[i] = INF;
        while(true)
        {
            memset(visx, false, sizeof(visx));
            memset(visy, false, sizeof(visy));
            if(dfs(x)) break;
            int d = INF;
            for(int i = 0; i < ny; i++)
                if(!visy[i] && d > slack[i])
                d = slack[i];
            for(int i = 0; i < nx; i++)
                if(visx[i]) lx[i] -= d;
            for(int i = 0; i < ny; i++)
                if(visy[i]) ly[i] += d;
                else slack[i] -= d;
        }
    }
    int res = 0;
    for(int i = 0; i < ny; i++)
        if(linker[i] != -1)
        res += g[linker[i]][i];
    return res;
}

粘俩题：

A.最大权匹配

P - 奔小康赚大钱 HDU - 2255

题意:卖房子，每套房子每个人给不同的钱，全卖出去赚最多的钱。

#include <iostream>
#include <cstdio>
#include <stack>
#include <cmath>
#include <set>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 510;

int g[maxn][maxn], linker[maxn], lx[maxn], ly[maxn];
int slack[maxn], nx, ny;
bool visx[maxn], visy[maxn];
bool dfs(int x)
{
    visx[x] = 1;
    for(int y = 0; y < ny; y++){
        if(visy[y]) continue;
        int tmp = lx[x] + ly[y] - g[x][y];
        if(tmp == 0){
            visy[y] = 1;
            if(linker[y] == -1 || dfs(linker[y])){
                linker[y] = x;
                return 1;
            }
        }
        else if(slack[y] > tmp) slack[y] = tmp;
    }
    return false;
}

int KM()
{
    memset(linker, -1, sizeof(linker));
    memset(ly, 0, sizeof(ly));
    for(int i = 0; i < nx; i++)
    {
        lx[i] = -INF;
        for(int j = 0; j < ny; j++)
            if(g[i][j] > lx[i]) lx[i] = g[i][j];
    }
    for(int x = 0; x < nx; x++){
        for(int i = 0; i < ny; i++)
            slack[i] = INF;
        while(true)
        {
            memset(visx, false, sizeof(visx));
            memset(visy, false, sizeof(visy));
            if(dfs(x)) break;
            int d = INF;
            for(int i = 0; i < ny; i++)
                if(!visy[i] && d > slack[i])
                d = slack[i];
            for(int i = 0; i < nx; i++)
                if(visx[i]) lx[i] -= d;
            for(int i = 0; i < ny; i++)
                if(visy[i]) ly[i] += d;
                else slack[i] -= d;
        }
    }
    int res = 0;
    for(int i = 0; i < ny; i++)
        if(linker[i] != -1)
        res += g[linker[i]][i];
    return res;
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
            scanf("%d", &g[i][j]);
        nx = ny = n;
        printf("%d\n", KM());
    }
    return 0;
}

B最小权最大匹配
Q - Tour HDU - 3488

题意：n条道路经过n个城市回到原点，然后问最小行程距离。

#include <iostream>
#include <cstdio>
#include <stack>
#include <cmath>
#include <set>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 510;

int g[maxn][maxn], linker[maxn], lx[maxn], ly[maxn];
int slack[maxn], nx, ny, t, n, m;
bool visx[maxn], visy[maxn];
bool dfs(int x)
{
    visx[x] = 1;
    for(int y = 0; y < ny; y++){
        if(visy[y]) continue;
        int tmp = lx[x] + ly[y] - g[x][y];
        if(tmp == 0){
            visy[y] = 1;
            if(linker[y] == -1 || dfs(linker[y])){
                linker[y] = x;
                return 1;
            }
        }
        else if(slack[y] > tmp) slack[y] = tmp;
    }
    return false;
}

int KM()
{
    memset(linker, -1, sizeof(linker));
    memset(ly, 0, sizeof(ly));
    for(int i = 0; i < nx; i++)
    {
        lx[i] = -INF;
        for(int j = 0; j < ny; j++)
            if(g[i][j] > lx[i]) lx[i] = g[i][j];
    }
    for(int x = 0; x < nx; x++){
        for(int i = 0; i < ny; i++)
            slack[i] = INF;
        while(true)
        {
            memset(visx, false, sizeof(visx));
            memset(visy, false, sizeof(visy));
            if(dfs(x)) break;
            int d = INF;
            for(int i = 0; i < ny; i++)
                if(!visy[i] && d > slack[i])
                d = slack[i];
            for(int i = 0; i < nx; i++)
                if(visx[i]) lx[i] -= d;
            for(int i = 0; i < ny; i++)
                if(visy[i]) ly[i] += d;
                else slack[i] -= d;
        }
    }
    int res = 0;
    for(int i = 0; i < ny; i++)
        if(linker[i] != -1)
        res += g[linker[i]][i];
    return res;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        for(int i = 0; i <= n; i++)
            for(int j = 0; j <= n; j++)
            g[i][j] = -INF;
        for(int i = 0; i < m; i++)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            if(g[a - 1][b - 1]) g[a - 1][b - 1] = max(g[a - 1][b - 1], -c);
            else g[a - 1][b - 1] = -c;
        }
        nx = ny = n;
        printf("%d\n", -KM());
    }
    return 0;
}