2879: [Noi2012]美食節(jié)

---

?

Time Limit:?10 Sec??Memory Limit:?512 MB
Submit:?2288??Solved:?1207
[Submit][Status][Discuss]

Description

---

?

CZ市為了歡迎全國各地的同學(xué)，特地舉辦了一場盛大的美食節(jié)。作為一個喜歡嘗鮮的美食客，小M自然不愿意錯過這場盛宴。他很快就嘗遍了美食節(jié)所有的美食。然而，嘗鮮的欲望是難以滿足的。盡管所有的菜品都很可口，廚師做菜的速度也很快，小M仍然覺得自己桌上沒有已經(jīng)擺在別人餐桌上的美食是一件無法忍受的事情。于是小M開始研究起了做菜順序的問題，即安排一個做菜的順序使得同學(xué)們的等待時間最短。小M發(fā)現(xiàn)，美食節(jié)共有n種不同的菜品。每次點(diǎn)餐，每個同學(xué)可以選擇其中的一個菜品。總共有m個廚師來制作這些菜品。當(dāng)所有的同學(xué)點(diǎn)餐結(jié)束后，菜品的制作任務(wù)就會分配給每個廚師。然后每個廚師就會同時開始做菜。廚師們會按照要求的順序進(jìn)行制作，并且每次只能制作一人份。此外，小M還發(fā)現(xiàn)了另一件有意思的事情: 雖然這m個廚師都會制作全部的n種菜品，但對于同一菜品，不同廚師的制作時間未必相同。他將菜品用1, 2, ..., n依次編號，廚師用1, 2, ..., m依次編號，將第j個廚師制作第i種菜品的時間記為 ti,j 。小M認(rèn)為：每個同學(xué)的等待時間為所有廚師開始做菜起，到自己那份菜品完成為止的時間總長度。換句話說，如果一個同學(xué)點(diǎn)的菜是某個廚師做的第k道菜，則他的等待時間就是這個廚師制作前k道菜的時間之和。而總等待時間為所有同學(xué)的等待時間之和。現(xiàn)在，小M找到了所有同學(xué)的點(diǎn)菜信息: 有 pi 個同學(xué)點(diǎn)了第i種菜品（i=1, 2, ..., n）。他想知道的是最小的總等待時間是多少。

Input

---

?

?

?輸入文件的第1行包含兩個正整數(shù)n和m，表示菜品的種數(shù)和廚師的數(shù)量。 第2行包含n個正整數(shù)，其中第i個數(shù)為pi，表示點(diǎn)第i種菜品的人數(shù)。 接下來有n行，每行包含m個非負(fù)整數(shù)，這n行中的第i行的第j個數(shù)為ti,j，表示第j個廚師制作第i種菜品所需的時間。 輸入文件中每行相鄰的兩個數(shù)之間均由一個空格隔開，行末均沒有多余空格。

Output

---

?

?輸出僅一行包含一個整數(shù)，為總等待時間的最小值。

Sample Input

---

?

3 2 3 1 1 5 7 3 6 8 9

?

Sample Output

---

?

47

?

【樣例說明】

---

廚師1先制作1份菜品2，再制作2份菜品1。點(diǎn)這3道菜的3個同學(xué)的等待時間分別為3，3+5=8，3+5+5=13。
廚師2先制作1份菜品1，再制作1份菜品3。點(diǎn)這2道菜的2個同學(xué)的等待時間分別為7，7+9=16。
總等待時間為3+8+13+7+16=47。
雖然菜品1和菜品3由廚師1制作更快，如果這些菜品都由廚師1制作，總等待時間反而更長。如果按上述的做法，將1份菜品1和1份菜品3調(diào)整到廚師2制作，這樣廚師2不會閑著，總等待時間更短。
可以證明，沒有更優(yōu)的點(diǎn)餐方案。


【數(shù)據(jù)規(guī)模及約定】

---

對于100%的數(shù)據(jù)，n <= 40, m <= 100, p <= 800, ti,j <= 1000（其中p = ∑pi，即點(diǎn)菜同學(xué)的總?cè)藬?shù)）。
每組數(shù)據(jù)的n、m和p值如下：
測試點(diǎn)編號 n m p
1 n = 5 m = 5 p = 10
2 n = 40 m = 1 p = 400
3 n = 40 m = 2 p = 300
4 n = 40 m = 40 p = 40
5 n = 5 m = 40 p = 100
6 n = 10 m = 50 p = 200
7 n = 20 m = 60 p = 400
8 n = 40 m = 80 p = 600
9 n = 40 m = 100 p = 800
10 n = 40 m = 100 p = 800
初步看法：

---

做法和SCOI2006修車類似，只是人數(shù)多了點(diǎn)，建邊建不下。 思路：

---

可以動態(tài)建邊，先把一個人第倒數(shù)第一修的加進(jìn)去，如果滿流了再加倒數(shù)第二個點(diǎn)。 然后也沒有必要拆成每個人，看作每道菜為一個點(diǎn)，建向匯點(diǎn)的流量為吃那個菜的人數(shù)。 最后做到整個圖只有40 * 900左右條邊 ? 貼上AC代碼：

---

# include <iostream> # include <cstdio> # include <queue> # include <cstring> using namespace std; const int N = 2e5; const int INF = 0x3f3f3f3f; const int M = 3e6; int head[N],n,m,cnt,inde; struct Edge{ int to,res,cost,next; }edge[M]; void AddEdge(int u,int to,int f,int c){ Edge E1 = {to,f,c,head[u]}; edge[inde] = E1; head[u] = inde++; Edge E2 = {u,0,-c,head[to]}; edge[inde] = E2; head[to] = inde++; } queue <int> Q; bool vis[N]; int dist[N]; int pre[N]; int s,t; bool Spfa(){ memset(dist,INF,sizeof (dist)); memset(vis,false,sizeof (vis)); memset(pre,-1,sizeof (pre)); int u; dist[s] = 0;vis[s] = true;Q.push(s); while(!Q.empty()){ u = Q.front();Q.pop();vis[u] = false; for(int i = head[u];i != -1;i = edge[i].next)if(dist[edge[i].to] > dist[u] + edge[i].cost && edge[i].res){ dist[edge[i].to] = dist[u] + edge[i].cost; pre[edge[i].to] = i; if(!vis[edge[i].to]){ vis[edge[i].to] = true; Q.push(edge[i].to); } } } return pre[t] != -1; } int num[42]; int food[102][42],p; int flow,cost; int c; void updata(){ int Min = INF; for(int i = pre[t];i != -1;i = pre[edge[i ^ 1].to]){ Min = min(Min,edge[i].res); if(edge[i ^ 1].to == s)c = edge[i].to; } for(int i = pre[t];i != -1;i = pre[edge[i ^ 1].to]){ edge[i].res -= Min; edge[i ^ 1].res += Min; cost += Min * edge[i].cost; } flow += Min; } void Dinic(){ while(Spfa()){ updata(); int a = (c - 1) / p,b = c % p + 1; if(b != 1){ AddEdge(s,a * p + b,1,0); for(int i = 1;i <= n;i++){ AddEdge(a * p + b,m * p + i,1,food[a][i] * b); } } } } int main(){ memset(head,-1,sizeof (head)); scanf("%d %d",&n,&m); s = 0; for(int i = 1;i <= n;i++){ scanf("%d",&num[i]); p += num[i]; } t = m * p + n + 1; for(int i = 1;i <= n;i++){ for(int j = 0;j < m;j++){ scanf("%d",&food[j][i]); } } for(int i = 0;i < m;i++){ AddEdge(s,i * p + 1,1,0); for(int j = 1;j <= n;j++) AddEdge(i * p + 1 ,m * p + j,1,food[i][j]); } for(int i = 1;i <= n;i++)AddEdge(m * p + i,t,num[i],0); Dinic(); printf("%d\n",cost); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lzdhydzzh/p/7614401.html

總結(jié)

以上是生活随笔為你收集整理的[NOI2012（bzoj2879）（vijos1726）]美食节 （费用流）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。