POJ 3686 最小權匹配

題意：有N個工作，可以由M個工廠完成，但是每個工廠一次只能完成一個工作，並且完成這個工作之前不能換別的工作。問完成時間的平均值最少是多少。 思路：很神奇的建圖，完全是突破天際了。 偶然間看到一種寫法，突然感覺這個代碼風格有點像魏神的，然後去他博客裡一搜，居然真是。 來個傳送門神牛博客 /*****以下轉自上述博客********/ 假設某個機器處理了k個玩具,那麼對於這些玩具，有兩種時間，一種是真正處理的時間，一種是等待的時間，等待的時間就是之前所有處理的玩具的時間， 假設這k個玩具真正用在加工的時間分為a1,a2,a3...ak, 那麼每個玩具實際的時間是加工的時間+等待時間，分別為 a1, a1+a2, a1+a2+a3.......a1+a2+...ak  求和之後變為 a1 *k + a2 * (k - 1) + a3 * (k - 2).... + ak  這時就發現，每個玩具之間的實際時間可以分開來算 然後求和了。 因為對每個機器，最多可以處理n個玩具，所以可以拆成n個點，1~n分別代表某個玩具在這個機器上倒數第幾個被加工的 所以我們對於每個玩具i，機器j中拆的每個點k，連接一條z[i][j]*k權值的邊。 /******轉完收工*******/ 建完圖就是最小權匹配了。  

#include <set>  
#include <map>  
#include <stack>  
#include <cmath>  
#include <queue>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <iomanip>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
#define Max 2505  
#define FI first  
#define SE second  
#define ll long long  
#define PI acos(-1.0)  
#define inf 0x3fffffff  
#define LL(x) ( x << 1 )  
#define bug puts("here")  
#define PII pair<int,int>  
#define RR(x) ( x << 1 | 1 )  
#define mp(a,b) make_pair(a,b)  
#define mem(a,b) memset(a,b,sizeof(a))  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
  
using namespace std;  
  
/*********************************************/  
#define N 2555  
#define eps 1e-8  
int n , m ;  
int Map[55][N] ;  
int lx[N] , ly[N] ,visx[N] , visy[N] , linkx[N] , linky[N] ;  
//int fk[N][N] ;  
int h ;  
int find(int now) {  
    visx[now] = 1 ;  
    for (int i = 1 ; i <= h ; i ++ ) {  
        if(!visy[i] && Map[now][i] - lx[now] - ly[i] == 0) {  
            visy[i] = 1 ;  
            if(linky[i] == -1 || find(linky[i])) {  
                linkx[now] = i ;  
                linky[i] = now ;  
                return 1 ;  
            }  
        }  
    }  
    return 0 ;  
}  
int KM() {  
    mem(linky ,-1) ;  
    mem(ly , 0) ;  
    for (int i = 1 ; i <= n ; i ++ ) {  
        while(1) {  
//            bug ;  
            mem(visx, 0) ;mem(visy ,0) ;  
            if(find(i))break ;  
            int d = inf ;  
            for (int j = 1 ; j <= n ; j ++ )  
                if(visx[j])  
                    for (int k = 1 ; k <= h ; k ++ )  
                        if(!visy[k])  
                            d = min(d , Map[j][k] - lx[j] - ly[k]) ;  
            for (int j = 1 ; j <= n ; j ++ ){  
                if(visx[j])lx[j] += d ;  
            }  
            for (int j = 1 ; j <= h ; j ++ ){  
                if(visy[j])ly[j] -= d ;  
            }  
        }  
    }  
    int ans = 0 ;  
    for (int i = 1 ; i <= h ; i ++ ){  
        if(linky[i] != -1)ans += Map[linky[i]][i] ;  
    }  
    return ans ;  
}  
int main() {  
    int t ;  
    cin >> t ;  
    while(t -- ) {  
        cin >> n >> m ;  
        mem(Map ,0) ;  
        int tt ;  
        for (int i = 1 ; i <= n ; i ++ ) {  
            for (int j = 1 ; j <= m ; j ++ ) {  
                scanf("%d",&tt) ;  
                for (int k = 1 ; k <= n ; k ++ ){  
                    Map[i][n * (j - 1) + k] = k * (tt) ;  
                }  
            }  
        }  
        h = n * m ;  
        for (int i = 1 ; i <= n ; i ++ ){  
            lx[i] = inf ;  
            for (int j = 1 ; j <= h ; j ++ ){  
                lx[i] = min(lx[i] , Map[i][j]) ;  
            }  
        }  
        int ans = KM() ;  
        printf("%.6f\n",ans * 1.0 / n) ;  
    }  
    return 0 ;  
}