原文地址：http://www.cnblogs.com/GXZlegend/p/6798411.html

---

題目描述

同一時刻有N位車主帶著他們的愛車來到了汽車維修中心。維修中心共有M位技術人員，不同的技術人員對不同的車進行維修所用的時間是不同的。現在需要安排這M位技術人員所維修的車及順序，使得顧客平均等待的時間最小。 說明：顧客的等待時間是指從他把車送至維修中心到維修完畢所用的時間。

輸入

第一行有兩個m,n，表示技術人員數與顧客數。 接下來n行，每行m個整數。第i+1行第j個數表示第j位技術人員維修第i輛車需要用的時間T。

輸出

最小平均等待時間，答案精確到小數點后2位。

樣例輸入

2 2
3 2
1 4

樣例輸出

1.50

---

題解

拆點+費用流

把m每個工人拆成n*m個，表示修倒數第n輛該修的車的工人m

這樣對于工人(i,j)，修第t輛車的代價為time[t][j]*i，因為該修的倒數第i輛車只對這相應后面的i輛車有影響。

據此建圖，S->工人:(1,0)，工人->車:(1,time[t][j]*i)，車->T:(1,0)，因為每輛車只被修1次，每名工人同一時刻只能修1輛車。

然后跑費用流就行。

注意別把n和m弄反了。

另：數組其實不用開這么大

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
queue<int> q;
int v[70][15] , head[10000] , to[1000000] , val[1000000] , cost[1000000] , next[1000000] , cnt = 1 , s , t , dis[10000] , from[10000] , pre[10000];
void add(int x , int y , int v , int c)
{to[++cnt] = y , val[cnt] = v , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt;to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt;
}
bool spfa()
{int x , i;memset(from , -1 , sizeof(from));memset(dis , 0x7f , sizeof(dis));dis[s] = 0 , q.push(s);while(!q.empty()){x = q.front() , q.pop();for(i = head[x] ; i ; i = next[i])if(val[i] && dis[to[i]] > dis[x] + cost[i])dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i , q.push(to[i]);}return ~from[t];
}
int mincost()
{int i , k , ans = 0;while(spfa()){k = 0x7f7f7f7f;for(i = t ; i != s ; i = from[i]) k = min(k , val[pre[i]]);ans += dis[t] * k;for(i = t ; i != s ; i = from[i]) val[pre[i]] -= k , val[pre[i] ^ 1] += k;}return ans;
}
int main()
{int n , m , i , j , k;scanf("%d%d" , &m , &n);s = 0 , t = n * m + n + 1;for(i = 1 ; i <= n ; i ++ ) add(i + n * m , t , 1 , 0);for(i = 1 ; i <= n ; i ++ )for(j = 1 ; j <= m ; j ++ )scanf("%d" , &v[i][j]) , add(s , (i - 1) * m + j , 1 , 0);for(i = 1 ; i <= n ; i ++ )for(j = 1 ; j <= n ; j ++ )for(k = 1 ; k <= m ; k ++ )add((j - 1) * m + k , i + n * m , 1 , v[i][k] * j);printf("%.2lf\n" , (double)mincost() / n);return 0;
}

?

轉載于:https://www.cnblogs.com/GXZlegend/p/6798411.html

總結

以上是生活随笔為你收集整理的【bzoj1070】[SCOI2007]修车 最小费用流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。