题目链接
拆点&＃43;KM&＃xff0c;建图思路看的题解。。。
看懂的题意后&＃xff0c;想了好一会。知道这题是KM&＃xff0c;但是不会建图&＃xff0c;无奈啊。
建图很巧妙&＃xff0c;假如同一个机器上加工了k件物品&＃xff0c;那么实际花费时间k*a1&＃43;(k-1)*a2&＃43;(k-3)*a3....
其实对这个拆点&＃xff0c;也不是很懂。
这样把m个机器拆成n个点&＃xff0c;表示是第几个加工的。套上模版&＃xff0c;这题是求最小权&＃xff0c;取一下相反数就行了。
拆成两个集合一个存n个物品&＃xff0c;另一个存第i个机器上第j个加工。
1 #include
2 #include
3 #include <string>
4 #include
5 #include
6 using namespace std;
7 #define N 2552
8 #define INF 0x7fffffff
9 int mat[N][N];
10 int inx[N],iny[N];
11 int lx[N],ly[N];
12 int match[N];
13 int n,m;
14 int inp[N][N];
15 int dfs(int u)
16 {
17 inx[u] &＃61; 1;
18 int i;
19 for(i &＃61; 1; i <&＃61; m*n; i &＃43;&＃43;)
20 {
21 if(!iny[i]&&lx[u]&＃43;ly[i] &＃61;&＃61; mat[u][i])
22 {
23 iny[i] &＃61; 1;
24 if(match[i] &＃61;&＃61; -1||dfs(match[i]))
25 {
26 match[i] &＃61; u;
27 return 1;
28 }
29 }
30 }
31 return 0;
32 }
33 void KM()
34 {
35 int i,j,k,temp;
36 for(i &＃61; 1;i
37 {
38 lx[i] &＃61; -INF;
39 ly[i] &＃61; -INF;
40 }
41 for(i &＃61; 1; i <&＃61; n; i &＃43;&＃43;)
42 {
43 for(j &＃61; 1; j <&＃61; m*n; j &＃43;&＃43;)
44 lx[i] &＃61; max(lx[i],mat[i][j]);
45 }
46 for(i &＃61; 1; i <&＃61; n; i &＃43;&＃43;)
47 {
48 for(;;)
49 {
50 memset(inx,0,sizeof(inx));
51 memset(iny,0,sizeof(iny));
52 if(dfs(i))
53 break;
54 else
55 {
56 temp &＃61; INF;
57 for(j &＃61; 1; j <&＃61; n; j &＃43;&＃43;)
58 {
59 if(inx[j])
60 {
61 for(k &＃61; 1; k <&＃61; m*n; k &＃43;&＃43;)
62 {
63 if(!iny[k]&&temp > lx[j]&＃43;ly[k]-mat[j][k])
64 temp &＃61; lx[j]&＃43;ly[k]-mat[j][k];
65 }
66 }
67 }
68 for(j &＃61; 1;j <&＃61; n;j &＃43;&＃43;)
69 {
70 if(inx[j])
71 lx[j] -&＃61; temp;
72 }
73 for(j &＃61; 1;j <&＃61; m*n;j &＃43;&＃43;)
74 {
75 if(iny[j])
76 ly[j] &＃43;&＃61; temp;
77 }
78 }
79 }
80 }
81 }
82 int main()
83 {
84 int i,j,k,cas;
85 scanf("%d",&cas);
86 while(cas--)
87 {
88 scanf("%d%d",&n,&m);
89 memset(match,-1,sizeof(match));
90 for(i &＃61; 1;i <&＃61; n;i &＃43;&＃43;)
91 {
92 for(j &＃61; 1;j <&＃61; m;j &＃43;&＃43;)
93 {
94 scanf("%d",&inp[i][j]);
95 }
96 }
97 for(i &＃61; 1;i <&＃61; n;i &＃43;&＃43;)
98 {
99 for(j &＃61; 1;j <&＃61; m;j &＃43;&＃43;)
100 {
101 for(k &＃61; 1;k <&＃61; n;k &＃43;&＃43;)
102 {
103 mat[i][(j-1)*n&＃43;k] &＃61; -((n-k&＃43;1)*inp[i][j]);
104 }
105 }
106 }
107 KM();
108 int ans &＃61; 0;
109 for(i &＃61; 1;i <&＃61; n*m;i &＃43;&＃43;)
110 {
111 if(match[i] !&＃61; -1)
112 ans &＃43;&＃61; mat[match[i]][i];
113 }
114 printf("%.6lf\n",-ans*1.0/n);
115 }
116 return 0;
117 }
京公网安备 11010802041100号