题解
这道题的费用流如果朴素一点怎么建边呢
建出\(\sum_{i = 1}^{n} p^{i} M\)个点，第\(i\)个厨师的第\(j\)个点表示这个厨师倒数第\(j\)个做的是某道菜
这个点向汇点流一条流量为1，费用为0的边
然后每个菜建出来一个点，源点向每个菜流容量为\(p\)，费用为0的点，第\(k\)个菜想第\(i\)个厨师的第\(j\)个点连 \(j * a[k][i]\)的边
比较好理解，因为最后一个菜的时间会被加一遍，倒数第二个菜会加两遍
但是这样会超时……我们尝试动态开点
我们初始化的时候只把所有厨师的倒数第一个菜建出来
由于我们有spfa跑最小费用最大流的时候，一定走了某个厨师的某个点，把这个厨师的下一道菜建出来就好了
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define enter putchar('\n')
#define space putchar(' ')
//#define ivorysi
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
const int MOD = 1000000007;
int N,M;
int a[45][105],p[45];
struct node {
int to,next,val,cap;
}E[2000005];
int head[40005],sumE = 1,Ncnt;
int S,T;
queue<int> Q;
bool inq[40005];
int dis[40005],pre[40005],dish[45],id[40005],chef[105],rk[105];
void add(int u,int v,int c,int a) {
E[++sumE].to = v;E[sumE].next = head[u];E[sumE].cap = c;E[sumE].val = a;
head[u] = sumE;
}
void addtwo(int u,int v,int c,int a) {
add(u,v,c,a);add(v,u,0,-a);
}
bool spfa() {
for(int i = 1 ; i <= Ncnt ; ++i) dis[i] = 0x7fffffff,pre[i] = 0;
dis[S] = 0;Q.push(S);
while(!Q.empty()) {
int u = Q.front();Q.pop();
inq[u] = 0;
for(int i = head[u] ; i ; i = E[i].next) {
if(E[i].cap) {
int v = E[i].to;
if(dis[v] > dis[u] + E[i].val) {
dis[v] = dis[u] + E[i].val;pre[v] = i;
if(!inq[v]) {inq[v] = 1;Q.push(v);}
}
}
}
}
return dis[T] < 0x7fffffff;
}
void Init() {
read(N);read(M);
S = ++Ncnt;T = ++Ncnt;
for(int i = 1 ; i <= N ; ++i) {
read(p[i]);dish[i] = ++Ncnt;
addtwo(S,dish[i],p[i],0);
}
for(int i = 1 ; i <= M ; ++i) {
id[++Ncnt] = i;
chef[i] = Ncnt;
rk[i] = 1;
}
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= M ; ++j) {
read(a[i][j]);
addtwo(dish[i],chef[j],1,a[i][j]);
}
}
for(int i = 1 ; i <= M ; ++i) addtwo(chef[i],T,1,0);
}
void Solve() {
int ans = 0;
while(spfa()) {
int flow = 0x7fffffff;
for(int p = T,i = pre[p] ; i ; p = E[i ^ 1].to,i = pre[p]) {
flow = min(E[i].cap,flow);
}
for(int p = T,i = pre[p] ; i ; p = E[i ^ 1].to,i = pre[p]) {
E[i].cap -= flow;
E[i ^ 1].cap += flow;
}
ans += flow * dis[T];
int t = id[E[pre[T] ^ 1].to];chef[t] = ++Ncnt;++rk[t];id[chef[t]] = t;
for(int i = 1 ; i <= N ; ++i) {
addtwo(dish[i],chef[t],1,rk[t] * a[i][t]);
}
addtwo(chef[t],T,1,0);
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
}