POJ 3686 The Windy's【最小权匹配（神建图啊）】

大意：有n个任务m个机器，告诉你n*m的矩阵表示每个任务在每个机器上完成需要的时间

问所有任务完成的总时间最少？（比如第一个任务在第一分钟完成第二个任务在第二分钟完成则总时间为1 + 2 = 3

分析：

该题自己做的时候没有思路

后来在网上搜题解，感觉建图真是太厉害了

假设最优情况下，个个任务需要的时间分别为a1， a2, a3, ……，an

那么总时间t = n * a1 + (n - 1) * a2 + ……+ 2 * an - 1 + an

也就是说只需要考虑系数就可以了

我们先假设只有一台机器

那么也就是为每个任务的时间选择一个不同的系数

也就是从每个任务向该机器建n条边分别表示系数边权值为k*cost即可

扩展为m台机器只要把每个机器拆成n个点就可以了~~

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <vector>
  5 using namespace std;
  6 
  7 const int maxn = 55;
  8 const int INF = 1000000000;
  9 
 10 int Sx[maxn], Sy[maxn * maxn];
 11 int Lx[maxn], Ly[maxn * maxn];
 12 int Link[maxn * maxn];
 13 int Lix[maxn];
 14 int W[maxn][maxn * maxn];
 15 int n, m;
 16 
 17 bool Find(int i) {
 18     Sx[i] = true;
 19     for(int j = 1; j <= m; j++) {
 20         if(!Sy[j] && Lx[i] + Ly[j] == W[i][j] ) {
 21             Sy[j] = true;
 22             if(Link[j] == 0 || Find(Link[j])) {
 23                 Lix[i] = j;
 24                 Link[j] = i;
 25                 return true;
 26             }
 27         }
 28     }
 29     return false;
 30 }
 31 
 32 int KM() {
 33     for(int i = 1; i <= n; i++) {
 34         Lx[i] = - INF;
 35         for(int j = 1; j <= m; j++) {
 36             Lx[i] = max(Lx[i], W[i][j]);
 37         }
 38     }
 39     memset(Ly, 0, sizeof(Ly));
 40     memset(Link, 0, sizeof(Link));
 41     for(int v = 1; v <= n; v++) {
 42         memset(Sx, 0, sizeof(Sx));
 43         memset(Sy, 0, sizeof(Sy));
 44         while(1) {
 45             if(Find(v)) break;
 46             int dmin = INF;
 47             for(int i = 1; i <= n; i++) {
 48                 if(Sx[i]) {
 49                     for(int j = 1; j <= m; j++) {
 50                         if(!Sy[j] && Lx[i] + Ly[j] - W[i][j] < dmin) {
 51                             dmin = Lx[i] + Ly[j] - W[i][j];
 52                         }
 53                     }
 54                 }
 55             }
 56             for(int i = 1; i <= n; i++) {
 57                 if(Sx[i]) {
 58                     Lx[i] -= dmin;
 59                     Sx[i] = 0;
 60                 }
 61             }
 62             for(int i = 1; i <= m; i++) {
 63                 if(Sy[i]) {
 64                     Ly[i] += dmin;
 65                     Sy[i] = 0;
 66                 }
 67             }
 68         }
 69     }
 70     int sum = 0;
 71     for(int i = 1; i <= n; i++) {
 72         sum += W[i][Lix[i]];
 73     }
 74     return sum;
 75 }
 76 
 77 int mat[maxn][maxn];
 78 int main() {
 79     int t;
 80     scanf("%d",&t);
 81     while(t--) {
 82         scanf("%d %d",&n, &m);
 83         for(int i = 1; i <= n; i++) {
 84             for(int j = 1; j <= m; j++) {
 85                 scanf("%d",&mat[i][j]);
 86             }
 87         }
 88         for(int k = 1; k <= n; k++) {
 89             for(int i = 1; i <= m; i++) {
 90                 for(int j = 1; j <= n; j++) {
 91                     W[k][(i - 1) * n + j] = - mat[k][i] * j;
 92                 }
 93             }
 94         }
 95         m = n * m;
 96         int ans1 = -KM();
 97         double ans = ans1 * 1.0 / n;
 98         printf("%.6f
",ans);
 99     }
100     return 0;
101 }

View Code