Time Limit:10 SecMemory Limit:512 MB
Submit:1453Solved:778
Description
CZ市為了歡迎全國各地的同學，特地舉辦了一場盛大的美食節。作為一個喜歡嘗鮮的美食客，小M自然不願意錯過這場盛宴。他很快就嘗遍了美食節所有的美食。然而，嘗鮮的欲望是難以滿足的。盡管所有的菜品都很可口，廚師做菜的速度也很快，小M仍然覺得自己桌上沒有已經擺在別人餐桌上的美食是一件無法忍受的事情。於是小M開始研究起了做菜順序的問題，即安排一個做菜的順序使得同學們的等待時間最短。小M發現，美食節共有n種不同的菜品。每次點餐，每個同學可以選擇其中的一個菜品。總共有m個廚師來制作這些菜品。當所有的同學點餐結束後，菜品的制作任務就會分配給每個廚師。然後每個廚師就會同時開始做菜。廚師們會按照要求的順序進行制作，並且每次只能制作一人份。此外，小M還發現了另一件有意思的事情: 雖然這m個廚師都會制作全部的n種菜品，但對於同一菜品，不同廚師的制作時間未必相同。他將菜品用1, 2, ..., n依次編號，廚師用1, 2, ..., m依次編號，將第j個廚師制作第i種菜品的時間記為 ti,j 。小M認為：每個同學的等待時間為所有廚師開始做菜起，到自己那份菜品完成為止的時間總長度。換句話說，如果一個同學點的菜是某個廚師做的第k道菜，則他的等待時間就是這個廚師制作前k道菜的時間之和。而總等待時間為所有同學的等待時間之和。現在，小M找到了所有同學的點菜信息: 有 pi 個同學點了第i種菜品（i=1, 2, ..., n）。他想知道的是最小的總等待時間是多少。
Input
輸入文件的第1行包含兩個正整數n和m，表示菜品的種數和廚師的數量。 第2行包含n個正整數，其中第i個數為pi，表示點第i種菜品的人數。 接下來有n行，每行包含m個非負整數，這n行中的第i行的第j個數為ti,j，表示第j個廚師制作第i種菜品所需的時間。 輸入文件中每行相鄰的兩個數之間均由一個空格隔開，行末均沒有多余空格。
Output
輸出僅一行包含一個整數，為總等待時間的最小值。
Sample Input
3 2
3 1 1
5 7
3 6
8 9
Sample Output
47
【樣例說明】
廚師1先制作1份菜品2，再制作2份菜品1。點這3道菜的3個同學的等待時間分別為3，3+5=8，3+5+5=13。
廚師2先制作1份菜品1，再制作1份菜品3。點這2道菜的2個同學的等待時間分別為7，7+9=16。
總等待時間為3+8+13+7+16=47。
雖然菜品1和菜品3由廚師1制作更快，如果這些菜品都由廚師1制作，總等待時間反而更長。如果按上述的做法，將1份菜品1和1份菜品3調整到廚師2制作，這樣廚師2不會閒著，總等待時間更短。
可以證明，沒有更優的點餐方案。
【數據規模及約定】
對於100%的數據，n <= 40, m <= 100, p <= 800, ti,j <= 1000（其中p = ∑pi，即點菜同學的總人數）。
每組數據的n、m和p值如下：
測試點編號 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
HINT
Source
題解：費用流+動態加邊
剛開始寫的單純的費用流TLE了。
於是只能用一些高大上的東西——動態加點。
其實這道題除了數據范圍，與scoi 2007 修車就是一個題。
建圖
源點->所有廚師拆成的點（一個廚師sigma pi ）容量為1，費用為0
每種菜->匯點 容量為1，費用為0
本來應該一個廚師拆成的每個點都與不同的菜連容量為1，費用為t[i][j]×k 的邊（k表示倒數第幾個做，因為倒數第一做只有這個人需要等,做這個菜的時間不會其他菜） ，但是我們發現其實這些邊最後一定有很多是不會走到的。
於是我們剛開始的時候只需要把倒數第一人，即t[i][j]連好就可以了。
每次增廣的時候，其實只要一個是做菜的其余都是退菜，所以我們需要找出源點的後一個點，然後計算出他屬於哪個廚師做的第幾道菜，比如是第一個廚師的第2道菜，那麼我們就把所有菜到第一個廚師的第3道菜的邊聯通，再繼續增廣就可以了。
#include
#include
#include
#include
#include
#define N 100003
#define M 1200000
#define inf 1000000000
using namespace std;
int n,m,tot,mincost;
int next[M],v[M],remain[M],c[M],sum,q[N];
int point[N],can[N],dis[N],last[N],p[N],T[50][120];
void add(int x,int y,int z,int k)
{
tot++; next[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=z; c[tot]=k;
tot++; next[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0; c[tot]=-k;
}
int addflow(int s,int t)
{
int now=t; int ans=inf;
int k,a,b;
while (now!=s)
{
ans=min(ans,remain[last[now]]);
if (v[last[now]^1]==s)
{
k=v[last[now]];
a=(k-1)/sum+1; b=(k)%sum+1;
}
now=v[last[now]^1];
}
now=t;
while (now!=s)
{
remain[last[now]]-=ans;
remain[last[now]^1]+=ans;
now=v[last[now]^1];
}
mincost+=ans*dis[t];
for (int i=1;i<=m;i++)
add((a-1)*sum+b,n*sum+i,1,b*T[i][a]);
}
bool spfa(int s,int t)
{
for (int i=s;i<=t;i++)
dis[i]=inf,can[i]=0;
dis[s]=0; can[s]=1;
int head=0,tail=0;
q[++tail]=s;
while (headdis[now]+c[i]&&remain[i])
{
dis[v[i]]=dis[now]+c[i];
last[v[i]]=i;
if (!can[v[i]])
{
can[v[i]]=1;
q[++tail]=v[i];
}
}
can[now]=0;
}
if (dis[t]==inf) return false;
return true;
}
int main()
{
scanf("%d%d",&m,&n);
tot=-1; sum=0;
memset(next,-1,sizeof(next)); memset(point,-1,sizeof(point));
for (int i=1;i<=m;i++) scanf("%d",&p[i]),sum+=p[i];
int num=100001;
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++) scanf("%d",&T[i][j]);
for(int i=1;i<=n*sum;i++)
add(0,i,1,0);
for(int i=1;i<=m;i++)
add(n*sum+i,num,p[i],0);
for(int i=1;i<=n;i++)
for(int k=1;k<=m;k++)
add((i-1)*sum+1,n*sum+k,1,T[k][i]);
while (spfa(0,num))
addflow(0,num);
printf("%d\n",mincost);
return 0;
}
