HDU Assignment(KM變形好題！！！！)



Assignment

題目鏈接：Click Here~

題目分析:

給出n個人m個任務(n<=m)，要你給每個人分配任務，每個人對每個任務都有一個效益。要求你求出n個人的最大效益。且一開始每個人手上都有一個任務，你在以後分配任務的時候，必須更換盡量少的任務使得每個人的任務效益最大。

算法分析：

一道顯然的二分匹配算法。用KM求出最大的效益就好了。

建模分析：

因為，在更換最少的任務前提下的最大效益。所以，我們可以把每個任務擴大K倍(K>n)。為了使得盡量保持原先分配的任務，所以要給原先分配的任務+1。為什麼這樣可以呢？因為，前面我們擴大了K倍了，且K>n。所以，實質+1這個只對原先相等的權值有作用的，這就是為什麼要K>n的原因。最後，在把結果除以K，就是結果。總結點減去結果求余K就是改變的數。為什麼呢？因為有數學知識知道原先的每個權值都乘以了一個K。所以，不是原先分配的任務都可以被K除盡，唯一剩下的就是原先分配剩下的那個+1的值。

ACM果然是個一群高智商的人，玩的蛋疼游戲！！！

#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 50 + 5;
const int INF = ~0U>>1;
const int K = MAXN+MAXN;
int n,m,W[MAXN][MAXN];
int slack,Lx[MAXN],Ly[MAXN],Link[MAXN];
bool S[MAXN],T[MAXN];
inline bool Match(int i)
{
    S[i] = true;
    for(int j = 1;j <= m;++j)if(!T[j]){
        int tmp = Lx[i]+Ly[j]-W[i][j];
        if(tmp==0){
            T[j] = true;
            if(Link[j]==-1||Match(Link[j])){
                Link[j] = i;
                return true;
            }
        }
        else if(tmp < slack)
            slack = tmp;
    }
    return false;
}
inline void Update(int d)
{
    for(int i = 1;i <= n;++i)
        if(S[i]) Lx[i] -= d;
    for(int j = 1;j <= m;++j)
        if(T[j]) Ly[j] += d;
}
bool EK()
{
    for(int i = 1;i <= n;++i){
        Lx[i] = 0;
        for(int j = 1;j <= m;++j)
            Lx[i] = max(Lx[i],W[i][j]);
    }
    memset(Link,-1,sizeof(Link));
    memset(Ly,0,sizeof(Ly));

    slack = INF;
    for(int i = 1;i <= n;++i){
        while(1){
            memset(S,false,sizeof(S));
            memset(T,false,sizeof(T));
            if(Match(i))
                break;
            if(slack==INF)
                return false;
            Update(slack);
        }
    }
    return true;
}
void Get(int& X,int& Y)
{
    int sum = 0;
    for(int i = 1;i <= m;++i){
        if(Link[i]!=-1)
            sum += W[Link[i]][i];
    }
    Y = sum/K - Y;
    X = n - sum%K;
}
int main()
{
//    freopen("Input.txt","r",stdin);
//    freopen("Out.txt","w",stdout);
    while(~scanf("%d%d",&n,&m))
    {
        memset(W,0,sizeof(W));
        for(int i = 1;i <= n;++i){
            for(int j = 1;j <= m;++j){
                scanf("%d",&W[i][j]);
                W[i][j] *= K;
            }
        }
        int x,X,Y = 0;
        for(int i = 1;i <= n;++i){
            scanf("%d",&x);
            Y += W[i][x]/K;
            W[i][x]++;
        }
        EK();
        Get(X,Y);
        printf("%d %d\n",X,Y);
    }
    return 0;
}