Problem S: 八中公司

Description

小W在八中开了一个兼职中心。现在他手下有N个工人。每个工人有N个工作可以选择，于是每个人做每个工作的效率是不一样的。做为CEO的小W的任务就是给每个人分配一个工作，保证所有人效率之和是最大的。N<=200

Input

第一行给出数字N
接下来N行N列，代表每个人工作的效率。

Output

一个数字，代表最大效率之和

Sample Input

4
62 41 86 94
73 58 11 12
69 93 89 88
81 40 69 13

Sample Output

329
二分图带权最大匹配裸题
输入的a[i]就相当于第i个女生对n个男生的期望值
//附上蒟蒻代码

#include <bits/stdc++.h>
using namespace std;
int n,w[1001][1001];
int lx[1001],ly[1001],matched[1001],slack[1001];
bool s[1001],t[1001];
bool match(int i) {//匈牙利算法 
    s[i]=1; //第i个女生打上标记
    for(int j=1; j<=n; j++)
    {
        int cnt=lx[i]+ly[j]-w[i][j];//求出gap值
        if(cnt==0&&!t[j])//如果gap值为0，且第J个男生在本轮没有被占用
        {
            t[j]=1;//打上标记
            if(!matched[j]||match(matched[j]))
                //如果男生J从来没有被许配，或者被许配的对象可以向后调整的话
            {
                matched[j]=i;
                //标记男生j被第i个女生占有
                return 1;
            }
        } 
        else
            slack[j]=min(slack[j],cnt);
    }
    return false;
}
void update() {
    int a=INT_MAX;
    for(int i=1; i<=n; i++)
        if(!t[i])//没有被选到（匹配失败了） 
            a=min(a,slack[i]);//求出最少要减（加）的期望值 
    for(int i=1; i<=n; i++)
    {
        if(s[i])lx[i]-=a;//女生降低期望值 
        if(t[i])ly[i]+=a;//男生增加期望值 
    }
}
void km() {
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            lx[i]=max(lx[i],w[i][j]);//求出女生最高期望值是多少 
    for(int i=1; i<=n; i++)
    {
        memset(slack,0x3f,sizeof(slack));
        while(1)
            //整体采用贪心算法，保证每次能使一个女生匹配成功
        {
            memset(s,0,sizeof(s));
            memset(t,0,sizeof(t));//注意每一轮s,t都要清空 
            if(match(i))
                break;
            else
                //调整标顶值
                update();
        }
    }
}
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++)
        scanf("%d",&w[i][j]);
    km();
    int ans=0;
    for(int i=1; i<=n; i++)
        ans+=lx[i]+ly[i];
    printf("%d",ans);
    return 0;
}