首页 > 代码库 > POJ 3686 The Windy's【最小权匹配（神建图啊）】
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\n",ans); 99 }100 return 0;101 }
POJ 3686 The Windy's【最小权匹配（神建图啊）】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。