洛谷P2050[NOI2012]美食节

如果没有做过修车（本题的弱化版），可以先去做一下。

大致思路就是把每个厨师拆成\(p\)个点，分别代表倒数第几个做哪道菜，然后从每种菜向厨师连边，倒数第几个的边权就是几倍的等待时间，最后跑一波费用流即可。

但本题的数据范围有些残酷，所以我们考虑动态加边。最多只会跑\(p\)次\(spfa\)，并且每次走最短路增广，所以很多边都是没有用的。首先把代表倒数第一个做的菜的边加上。然后，比如某一次跑完\(spfa\)后，是沿第\(j\)个厨师的倒数第\(k\)个增广的，那就把他的代表倒数\(k+1\)的边补全。

代码如下：

#include
using namespace std;
#define N 40
#define M 100
#define P 800
#define SZ (N+P*M)
#define pb push_back
#define INF 0x3f3f3f3f
struct Edge
{
int from, to, cap, cost;
};
int n, m, tot, S, T, ans, ans0, t[N+5], d[SZ+5], vis[SZ+5], a[SZ+5], pre[SZ+5], tim[M+5][N+5], lim[M+5];
vector G[SZ+5];
vector edges;
int ID(int j, int k)
{
return n+(j-1)*tot+k;
}
int rev(int id)
{
return (id-n-1)/tot+1;
}
void addEdge(int u, int v, int cap, int cost)
{
edges.pb(Edge{u, v, cap, cost}), edges.pb(Edge{v, u, 0, -cost});
G[u].pb(edges.size()-2), G[v].pb(edges.size()-1);
}
int spfa()
{
memset(d, 0x3f, sizeof d);
d[S] = 0, vis[S] = 1, a[S] = INF, pre[S] = 0;
queue q; q.push(S);
while(!q.empty())
{
int u = q.front(); q.pop();
vis[u] = 0;
for(int i = 0, v, w; i {
Edge &e = edges[G[u][i]]; v = e.to, w = e.cost;
if(e.cap > 0 && d[v] > d[u]+w)
{
d[v] = d[u]+w;
a[v] = min(a[u], e.cap);
pre[v] = G[u][i];
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
if(d[T] == INF) return 0;
int u = T;
ans0 += a[T], ans += d[T]*a[T];
while(u != S)
{
edges[pre[u]].cap -= a[T], edges[pre[u]^1].cap += a[T];
u = edges[pre[u]].from;
}
return 1;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("testdata.in", "r", stdin);
freopen("testdata.out", "w", stdout);
#endif
scanf("%d%d", &n, &m);
S = 0;
for(int i = 1; i <= n; ++i) scanf("%d", &t[i]), tot += t[i], addEdge(S, i, t[i], 0);
T = n+tot*m+1;
for(int i = 1; i <= n; ++i)
{
for(int j = 1, t; j <= m; ++j) scanf("%d", &tim[j][i]), addEdge(i, ID(j, 1), 1, tim[j][i]), lim[j] = 1;
}
for(int i = n+1; i <= n+tot*m; ++i) addEdge(i, T, 1, 0);
while(spfa())
{
int j = rev(edges[pre[T]].from);
lim[j]++;
for(int i = 1; i <= n; ++i) addEdge(i, ID(j, lim[j]), 1, lim[j]*tim[j][i]);
}
printf("%d\n", ans);
return 0;
}