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）。他想知道的是最小的總等待時間是多少。

---

首先回憶一下1070: [SCOI2007]修車

把每個廚師拆成個點\(p\)，第i個點表示做這個廚師的倒數第\(i\)道菜

那么這個點對于答案的貢獻就是做這道菜所花時間的\(i\)倍

然后喜提TLE（...）

可以發現在倒數第一個還沒有流過的情況下倒數第二個是不可能被流到的！

動態加點就行了

---

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define MP make_pair #define TS top().second #define M 100000 #define N 100000 using namespace std;priority_queue<pair<int,int> >q; int cn,a[1000][1000],cc[1000],sum,t,n,m,k,ver[M],edge[M],head[N],nex[M],cnt=1,d[N],h[N],c[M],g[N],x,y,z,s,b[N],cur[N],ans,cost,w[M],bb[M]; void add(int x,int y,int co,int z) {ver[++cnt]=y; nex[cnt]=head[x]; head[x]=cnt; edge[cnt]=z; c[cnt]=co;ver[++cnt]=x; nex[cnt]=head[y]; head[y]=cnt; edge[cnt]=0; c[cnt]=-co; }bool dji() {while(q.size()) q.pop();memset(d,0,sizeof(d)); memset(g,0x3f,sizeof(g)); memset(b,0,sizeof(b));d[0]=1; g[0]=0; q.push(MP(0,0));while(q.size()){while(q.size() && b[q.TS]) q.pop();if(!q.size()) break;int x=q.TS; q.pop(); b[x]=1;for(int i=head[x];i;i=nex[i])if(edge[i] && g[ver[i]]>g[x]+c[i]+h[x]-h[ver[i]]){g[ver[i]]=g[x]+c[i]+h[x]-h[ver[i]];d[ver[i]]=d[x]+1;q.push(MP(-g[ver[i]],ver[i]));}}if(g[t]<0x3f3f3f3f) return 1;return 0; }int dinic(int x,int flow) {if(x==t || !flow) return flow;int re=flow, k;for(int& i=cur[x];i && re;i=nex[i])if(edge[i] && d[ver[i]]==d[x]+1 && g[ver[i]]==g[x]+c[i]+h[x]-h[ver[i]]){k=dinic(ver[i],min(re,edge[i]));if(k && ver[i]==t) bb[++bb[0]]=w[x];re-=k; edge[i]-=k; edge[i^1]+=k;if(!k) d[ver[i]]=0;} return flow-re; }int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&k),add(0,i,0,k), sum+=k;t=sum*m+n+1; cn=n+m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);add(i,j+n,a[i][j],1);}for(int i=1;i<=m;i++) cc[i]=1,add(i+n,t,0,1),w[i+n]=i;while(dji()){bb[0]=0;memcpy(cur,head,sizeof(head)); z=ans;while(k=dinic(0,0x3f3f3f3f)) ans+=k;for(int i=1;i<=cn;i++) {h[i]=g[i]+h[i]; if(g[i]==0x3f3f3f3f) h[i]=0;}h[t]+=g[t]; cost+=(ans-z)*h[t];for(int i=1;i<=bb[0];i++){int x=bb[i]; w[++cn]=bb[i];for(int j=1;j<=n;j++) add(j,cn,a[j][x]*(cc[x]+1),1);add(cn,t,0,1);cc[x]+=1;}}printf("%d",cost); }

轉載于:https://www.cnblogs.com/ZUTTER/p/10279510.html

總結

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

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