FFF NOJ 2073 裸KM算法

FFF

时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 157 测试通过 : 15

题目描述

FFF团，一个异端审判组织，团员活跃在各个角落，每当烧烤节来临的时候，我们都能听到他们传播的那熟悉的旋律：

烧啊~烧啊~烧啊烧啊烧~ (请自行脑补《当》)

FFF团成员自带这样一个属性：凭空变出火把与汽油，两者配合起来才能让FFF之火duang的一下烧起来，但是不同的火把与不同的汽油配合产生的火焰是不同的，现在有n种火把与n种汽油，已知每一种火把与每一种汽油配合时产生的火焰的旺盛程度，现在求怎样使得火把与汽油一一配对，产生最旺盛的火焰。

输入

第一行为一个整数T，表示有T组数据

每组数据第一行为一个正整数n（2≤n≤30）

第二行开始一共有n行，每行为n个正整数，第i行第j个数表示第i种火把与第j种汽油配合的火焰的旺盛程度。(0<a[i][j]≤10000)

输出

每组数据输出一个整数，表示最大的火焰旺盛程度

样例输入

2
3
5 2 6
6 7 9
7 4 1
4
8 5 2 8
5 8 2 1
9 6 3 7
7 5 8 1

样例输出

20
33

裸KM算法即可实现，听学长说最大费用最大流也可以==不过窝不会写

这里有KM模板，附上实现代码：

#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <cmath>

#define ll long long
int const N = 35;
int const M = 100005;
int const INF = 0x3f3f3f3f;
ll const mod = 1000000007;

using namespace std;

int T;
int n;
int nx,ny;       //??????????
int g[N][N];    //??????????
int linker[N],lx[N],ly[N];      //y????????????????x,y??????????
int slack[N];
bool visx[N],visy[N];

bool DFS(int x)
{
    visx[x] = true;
    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] = true;
            if(linker[y] == -1 || DFS(linker[y]))
            {
                linker[y] = x;
                return true;
            }
        }
        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;
}

void ini()
{
    scanf("%d",&n);
    int i,j;
    for(i = 0;i < n;i++){
        for(j = 0;j < n;j++)
            scanf("%d",&g[i][j]);
    }
    nx = ny =n;
}

void solve()
{

}

void out()
{
    printf("%d
",KM());
}

int main()
{
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    scanf("%d",&T);
    //for(int cnt=1;cnt<=T;cnt++)
    while(T--)
    //while(scanf("%d%d%d",&a,&b,&n)!=EOF)
    {
        ini();
        solve();
        out();
    }
}