学步园

POJ_3686

    看到这个题目后，首先一个思路就是相当于安排每个东西是第几次交给哪个机器做，这样就可以把每个机器拆成N个点当成二分图匹配的题目来做了。但是遇到的最大的问题就是，每个东西的总制造时间会依赖与前面制造的东西，这样每个东西的制造时间就不能独立计算，也就不能用二分图匹配去做了。

    但实际上计算这些东西总的制造时间还有另外一种方式，就是对于每个物品而言，除了计算它本身消耗的时间，同时计算上后面的物品会因为它的制造而额外增加的时间。比如如果制造当前这个物品需要的时间是t，而后面还有k个物品要制造，那么就等同于这个物品一共消耗了t+k*t的时间。这样转化之后就会发现计算每个物品的制造时间就仅仅依赖与后面有多少个物品，而不再依赖于这些物品是什么了，这样就可以用二分图匹配来做了：将每个机器都拆成N个点，分别表示是倒数第几次在这个机子上做的，然后建图用KM求解二分图最优匹配即可。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 60
#define MAXM 2510
#define INF 0x3f3f3f3f
int N, M, xM[MAXN], yM[MAXM], g[MAXN][MAXN], G[MAXN][MAXM], MAX;
int A[MAXN], B[MAXM], slack, visx[MAXN], visy[MAXM];
void init()
{
    int i, j, k;
    MAX = 0;
    scanf("%d%d", &N, &M);
    for(i = 1; i <= N; i ++)
        for(j = 1; j <= M; j ++)
        {
            scanf("%d", &g[i][j]);
            MAX = std::max(MAX, g[i][j] * N);
        }
    for(i = 1; i <= N; i ++)
        for(j = 1; j <= M; j ++)
            for(k = 1; k <= N; k ++)
                G[i][N * (j - 1) + k] = MAX - k * g[i][j];
}
int searchpath(int cur)
{
    int i;
    visx[cur] = 1;
    for(i = 1; i <= N * M; i ++)
        if(!visy[i])
        {
            int t = A[cur] + B[i] - G[cur][i];
            if(t == 0)
            {
                visy[i] = 1;
                if(yM[i] == -1 || searchpath(yM[i]))
                {
                    yM[i] = cur, xM[cur] = i;
                    return 1;
                }
            }
            else
                slack = std::min(slack, t);
        }
    return 0;
}
void solve()
{
    int i, j, ans = 0;
    memset(yM, -1, sizeof(yM));
    memset(B, 0, sizeof(B));
    for(i = 1; i <= N; i ++)
    {
        A[i] = 0;
        for(j = 1; j <= N * M; j ++) A[i] = std::max(A[i], G[i][j]);
    }
    for(i = 1; i <= N; i ++)
        for(;;)
        {
            slack = INF;
            memset(visx, 0, sizeof(visx));
            memset(visy, 0, sizeof(visy));
            if(searchpath(i)) break;
            for(j = 1; j <= N; j ++) if(visx[j]) A[j] -= slack;
            for(j = 1; j <= N * M; j ++) if(visy[j]) B[j] += slack;    
        }
    for(i = 1; i <= N; i ++) ans += MAX - G[i][xM[i]];
    printf("%.6f\n", (double)ans / N);
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t --)
    {
        init();
        solve();    
    }
    return 0;
}