codevs 1028 花店橱窗布置 KM算法

题目链接

n个花， m个花瓶， 每个花放到一个花瓶里会产生一个值w[i][j], 一个花只能放到一个花瓶里， 一个花瓶只能放一个花， 求产生的最大值。

带权二分图模板。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

const int M = ;

bool sx[M], sy[M];

int match[M], w[M][M], n, m, d, lx[M], ly[M];

void init ()

{

    memset (w, , sizeof(w));

}

bool dfs (int u)

{

    int v; sx[u] = true;

    for (v = ; v < m; v++)

    {

        if (!sy[v] && lx[u]+ly[v]==w[u][v])

        {

            sy[v] = true;

            if (match[v] == - || dfs (match[v]))

            {

                match[v] = u;

                return true;

            }

        }

    }

    return false;

}

int KM ()

{

    int i, j, k, sum = ;

    memset (ly, , sizeof(ly));

    for (i = ; i < n; i++)

    {

        lx[i] = -inf;

        for (j = ; j < m; j++)

            if (lx[i] < w[i][j])

                lx[i] = w[i][j];

    }

    memset (match, -, sizeof(match));

    for (i = ; i < n; i++)

    {

        while ()

        {

            memset (sx, false, sizeof(sx));

            memset (sy, false, sizeof(sy));

            if (dfs (i))

                break;

            d = inf;

            for (j = ; j < n; j++)

                if (sx[j])

                    for (k = ; k < m; k++)

                        if (!sy[k])

                            d = min (d, lx[j]+ly[k]-w[j][k]);

            if (d == inf)

                return -;

            for (j = ; j < n; j++)

                if (sx[j])

                    lx[j] -= d;

            for (j = ; j < m; j++)

                if (sy[j])

                    ly[j] += d;

        }

    }

    for (i = ; i < m; i++)

        if (match[i] > -)

            sum += w[match[i]][i];

    return sum;

}

int main()

{

    cin>>n>>m;

    for(int i = ; i<n; i++) {

        for(int j = ; j<m; j++) {

            scanf("%d", &w[i][j]);

        }

    }

    int ans = KM();

    cout<<ans<<endl;

    return ;

}