首页 > 代码库 > POJ 3686 The Windy's【最小权匹配（神建图啊）】

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

2024-07-19 17:03:03   219人阅读

大意：有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\n",ans); 99     }100     return 0;101 }
View Code

 

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


联系
我们