Description

CZ 市為了歡迎全國各地的同學，特地舉辦了一場盛大的美食節。

作為一個喜歡嘗鮮的美食客，小 M 自然不愿意錯過這場盛宴。他很快就嘗遍了美食節所有的美食。然而， 嘗鮮的欲望是難以滿足的。盡管所有的菜品都很可口，廚師做菜的速度也很快，小 M 仍然覺得自己桌上沒有已經擺在別人餐桌上的美食是一件無法忍受的事情。于是小 M 開始研究起了做菜順序的問題，即安排一個做菜的順序使得同學們的等待時間最短。

小 M 發現，美食節共有 n n 種不同的菜品。每次點餐，每個同學可以選擇其中的一個菜品。總共有 mm 個廚師來制作這些菜品。當所有的同學點餐結束后，菜品的制作任務就會分配給每個廚師。然后每個廚師就會同時開始做菜。 廚師們會按照要求的順序進行制作，并且每次只能制作一人份。

此外，小 M 還發現了另一件有意思的事情——雖然這 m m 個廚師都會制作全部的 nn 種菜品，但對于同一菜品，不同廚師的制作時間未必相同。他將菜品用 1,2,…,n 1 , 2 , … , n 依次編號，廚師用 1,2,…,m 1 , 2 , … , m 依次編號，將第 j j 個廚師制作第 i 種菜品的時間記為 Ti,jTi,j 。

小 M 認為：每個同學的等待時間為所有廚師開始做菜起，到自己那份菜品完成為止的時間總長度。換句話說，如果一個同學點的菜是某個廚師做的第 k k 道菜，則他的等待時間就是這個廚師制作前 kk 道菜的時間之和。 而總等待時間為所有同學的等待時間之和。

現在，小 M 找到了所有同學的點菜信息——有 ai a i 個同學點了第 i i 種菜品（i=1,2,…,ni=1,2,…,n） 。他想知道的是最小的總等待時間是多少。

Input

輸入文件的第 1 1 行包含兩個正整數 nn 和 m m ，表示菜品的種數和廚師的數量。

第 22 行包含 n n 個正整數，其中第 ii 個數為 ai a i ，表示點第 i i 種菜品的人數。

接下來有 nn 行，每行包含 m m 個非負整數，這 nn 行中的第 i i 行的第 jj 個數為 Ti,j T i , j ，

表示第 j? j 個廚師制作第 i i 種菜品所需的時間。

輸入文件中每行相鄰的兩個數之間均由一個空格隔開，行末均沒有多余空格。

Output

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

Data Constraint

對于 100% 100% 的數據， n≤40,m≤100,a≤800,ti,j≤1000 n ≤ 40 , m ≤ 100 , a ≤ 800 , t i , j ≤ 1000 (其中 a=∑ai? a = ∑ a i ,即點菜同學的總人數)。

Sample Input

3 2

3 1 1

5 7

3 6

8 9

Sample Output

47

Hint

廚師 1 1 先制作 11 份菜品 2 2 ，再制作 22 份菜品 1 1 。點這 33 道菜的 3 3 個同學的等待時間分別為 3，3+5=8，3+5+5=133，3+5=8，3+5+5=13。

廚師 2 2 先制作 11 份菜品 1 1 ，再制作 11 份菜品 3 3 。點這 22 道菜的 2 2 個同學的等待時間分別為 7，7+9=167，7+9=16。

總等待時間為 3+8+13+7+16=47 3 + 8 + 13 + 7 + 16 = 47 。

雖然菜品 1 1 和菜品 33 由廚師 1 1 制作更快，如果這些菜品都由廚師 11 制作，總等待時間反而更長。如果按上述的做法，將 1 1 份菜品 11 和 1 1 份菜品 33 調整到廚師 2 2 制作，這樣廚師 22 不會閑著，總等待時間更短。

可以證明，沒有更優的點餐方案。

Solution

很明顯是一道網絡流題目，先闡述連邊方法：

對于每個廚師，后做的菜不會影響前面做的菜，所以先從倒數第一時刻連邊。
為什么不能一下把所有時刻的邊連好呢？因為邊數太多啦！（屈指一算大約有 n?(m?∑a[i]+1) n ? ( m ? ∑ a [ i ] + 1 ) 條邊！）
所以思路就是，如果某廚師沒做第 ?i? i 道菜，那他就不可能做第 ?i+1? i + 1 道菜。每做一道菜，就為前一道菜（時刻）連邊繼續做流，且費用為 Ci?ti,j C i ? t i , j ， Ci C i 為倒數第幾道。

Code

var s,ans,n,m,tot,p,i,j:longint;dt,xx,yy,cont1,cont2,next,g,path:array[0..2000000] of longint;vis:array[0..100005] of boolean;dis:array[0..100005] of longint;a:array[1..100] of longint;t:array[1..100,1..100] of longint; procedure make(x,y,liu,fei:longint); begininc(tot);xx[tot]:=x;yy[tot]:=y;cont1[tot]:=liu;cont2[tot]:=fei;next[tot]:=g[x];g[x]:=tot; end; procedure init; var i,j:longint; beginreadln(n,m);for i:=1 to n do beginread(a[i]);inc(p,a[i]);end;for i:=1 to m do beginmake(0,(i-1)*p+1,1,0);make((i-1)*p+1,0,0,0);end;readln;for i:=1 to n do beginfor j:=1 to m do beginread(t[i,j]);make(p*(j-1)+1,p*m+i,1,t[i,j]);make(p*m+i,p*(j-1)+1,0,-t[i,j]);end;make(p*m+i,p*m+n+1,a[i],0);make(p*m+n+1,p*m+i,0,0);readln;end; end; function bfs:boolean; var l,r,i,j,x,y,mm:longint; begindt[1]:=s;fillchar(dis,sizeof(dis),127);fillchar(vis,sizeof(vis),false);mm:=dis[1];dis[0]:=1;l:=0;r:=1;vis[0]:=true;while l<r do begininc(l);if l=100000 then l:=0;x:=dt[l];i:=g[x];while i<>0 do beginy:=yy[i];if (cont2[i]+dis[x]<dis[y]) and (cont1[i]<>0) then begindis[y]:=dis[x]+cont2[i];path[y]:=i;if not vis[y] then begininc(r);if r=100000 then r:=0;dt[r]:=y;vis[y]:=true;end;end;i:=next[i];end;vis[x]:=false;end;if dis[m*p+n+1]=mm then exit(false) else exit(true); end; procedure fl; var i,x,y,v,qv,ci:longint; beginx:=path[m*p+n+1];v:=maxlongint;while x<>0 do beginif v>cont1[x] then v:=cont1[x];if xx[x]=0 then beginy:=yy[x];qv:=(y-1) div p+1;ci:=y mod p+1;end;x:=path[xx[x]];end;x:=path[m*p+n+1];while x<>0 do begindec(cont1[x],v);inc(cont1[x xor 1],v);ans:=ans+cont2[x]*v;x:=path[xx[x]];end;make(0,(qv-1)*p+ci,1,0);make((qv-1)*p+ci,0,0,0);for i:=1 to n do beginmake((qv-1)*p+ci,m*p+i,1,ci*t[i,qv]);make(m*p+i,(qv-1)*p+ci,0,-ci*t[i,qv]);end; end; begintot:=1;init;while bfs do fl;writeln(ans); end.

總結

以上是生活随笔為你收集整理的【NOI2012】美食节的全部內容，希望文章能夠幫你解決所遇到的問題。

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