POJ 3686

题意

• n个订单,m个工厂,第i 个订单在第j个工厂生产时间为g[i][j],工厂同一时间只能生产一个订单,但可以连续处理不同订单,如果都在一个工厂生产.即订单a生产完后才能生产b订单，b订单要等待a订单生产
• 求处理所有订单的最少时间？输出平均时间

思路(借鉴大神)

• 将每个工厂分为n个点,每个点代表第k个处理的商品,T=t1+(t1+t2)+(t1+t2+t3)+...等价于T=n*t1+(n-1)*t2+(n-2)*t3+....将订单等待时间通过公式转化成边权,

• 建立二分图,因为求最少时间,将边权改为负值就能求二分图的带权最大匹配

• 建图方法:

• POJ编译器版本问题,c++提交才通过.

• 个人的KM算法学习

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stdio.h>

using namespace std;
const int maxn = 52;
const int inf = 0x3f3f3f3f;
int g[maxn][maxn],w[maxn*maxn][maxn*maxn],la[maxn*maxn],lb[maxn*maxn],match[maxn*maxn];
bool va[maxn*maxn],vb[maxn*maxn];

int n,m,delta;

void init() {
    memset(match,-1,sizeof match);
    memset(la,0,sizeof la);
    memset(lb,0,sizeof lb);
}

int dfs(int u) {
    va[u] = 1;
    for (int i=0; i<m; ++i) {
        if (!vb[i]) {
            if (la[u]+lb[i] == w[u][i]) {
                vb[i] = 1;
                if (match[i]==-1 || dfs(match[i])) {
                    match[i] = u;
                    return 1;
                }
            } else delta = min(delta,la[u]+lb[i]-w[u][i]);
        }
    }
    return 0;
}

double KM() {
    for (int i=0; i<n; ++i) {
        while (1) {
            memset(va,0,sizeof va);
            memset(vb,0,sizeof vb);
            delta = inf;
            if (dfs(i)) break;
            for (int j=0; j<m; ++j) {
                if (va[j]) la[j] -= delta;
                if (vb[j]) lb[j] += delta;
            }
        }
    }
    double ans = 0.0;
    for (int i=0; i<m; ++i)
        if (match[i] != -1) ans += w[match[i]][i];
    return -ans;
}

int main() {
    freopen("1.in","r",stdin);
    int times; scanf("%d",&times);
    while (times--) {
        init();
        //cin >> n >> m;
        scanf("%d%d",&n,&m);
        for (int i=0; i<n; ++i)
            for (int j=0; j<m; ++j)
                scanf("%d",&g[i][j]);
        // n个订单, m个工厂
        for (int i=0; i<n; ++i)
            for (int k=0; k<n; ++k) // 倒数第k个订单
                for (int j=0; j<m; ++j)
                    w[i][j*n+k] = -(g[i][j]*(k+1)); //第i个订单在第J家公司生产，且是倒数第k个生产
        m = n*m;
        printf("%.6lf\n",KM()/(1.0*n));
    }
    return 0;
}