Assignment HDU - 2853（二分图匹配 KM 新边旧边）

传送门：

Assignment

题意:题意直接那松神的题意了。给了你n个公司和m个任务，然后给你了每个公司处理每个任务的效率。然后他已经给你了每个公司的分配方案，让你求出最多能增大多少效率（即最大权值匹配减去原来的），然后问你至少要修改多少个关系（即修改多少条边）

思路：关键在于最小修改的老边，很巧妙的将老边和新边的权值做了修改，使得并且不改变km里面的顺序，可以说是很巧妙的了。之后就就直接跑km的板子就好了，挺好的题目，难在新旧边的处理。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<stack>

#include<map>

#include<cstdlib>

#include <vector>

#include<queue>

using namespace std;

const int INF = 0x3f3f3f3f;

const int maxn = 1e3+;

int nx,ny,k;

int g[maxn][maxn];

int linker[maxn],lx[maxn],ly[maxn];

int slack[maxn];

bool visx[maxn],visy[maxn];

map<pair<int,int>,int>mp;

bool dfs(int x)

{

    visx[x] =  true;

    for(int y=;y<=ny;y++)

    {

        if(visy[y])

            continue;

        int tmp = lx[x] + ly[y] -g[x][y];

        if(tmp == )

        {

            visy[y] = true;

            if(linker[y] == - || dfs(linker[y]))

            {

                linker[y]  = x;

                return true;

            }

        }

        else if(slack[y] > tmp)

            slack[y] = tmp;

    }

    return false;

}

int KM()

{

    memset(linker,-,sizeof linker);

    memset(ly,,sizeof ly);

    for(int i=;i<=nx;i++)

    {

        lx[i] = -INF;

        for(int j=;j<=ny;j++)

        {

            if(g[i][j] > lx[i])

                lx[i] = g[i][j];

        }

    }

    for(int x = ;x <= nx ;x++)

    {

        for(int i=;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 = ;i <= ny;i ++ )

                if(!visy[i] && d > slack[i])

                    d = slack[i];

            for(int i = ;i <= nx; i++)

                if(visx[i])

                    lx[i] -= d;

            for(int i = ; i <= ny; i++)

            {

                if(visy[i])

                    ly[i] += d;

                else

                    slack[i] -= d;

            }

        }

    }

    int res = ;

    for(int i = ; i <= ny; i++)

        if(linker[i] != -)

            res += g[linker[i]][i];

    return res;

}

int main()

{

    int n,m;

    while(~scanf("%d%d",&n,&m))

    {

        mp.clear();

        memset(g,,sizeof g);

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

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

                int a;

                scanf("%d", &a);

                mp[make_pair(i, j)] = a;

                g[i][j] = a * (n + );

            }

        }

        int sum = ;

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

        {

            int b;

            scanf("%d",&b);

            g[i][b] += ;

            sum += mp[make_pair(i,b)];

        }

        nx = n;

        ny = m;

        int ans = KM();

        printf("%d %d\n",n-ans%(n+),ans/(n+)-sum);

    }

}