Address

洛谷P2050
BZOJ2879
LOJ#2674

Solution

一看发现和 SCOI2007 修车 是一样的。
这里再说一下建图：
把每个厨师拆成 ∑ i = 1 n p i \sum_{i=1}^np_i ∑i=1n​pi​ 个点，拆出的第 $i$ 个点表示倒数第 $i$ 个时刻的该厨师。
（1）由源点向每个时刻的厨师连一条容量为 $1$ 费用为 $0$ 的边，这限制了每个厨师每个时刻只能做一人份。
（2）由第 $i$ 个菜品向汇点连容量为 p i p_i pi​ 费用为 $0$ 的边，这表示第 $i$ 个菜品要做 p i p_i pi​ 份。
（3）由倒数 $j$ 时刻的第 $i$ 个厨师向第 $k$ 个菜品连边，容量为 $1$ ，费用为 j × t k , i j\times t_{k,i} j×tk,i​ ，这表示倒数 $j$ 时刻做菜会有 $j$ 倍的等待时间。
看上去一样，但是：数据变大了。
如果直接建图，则边数会达到 6.4 × 1 0 6 6.4\times 10^6 6.4×106 级别，啃腚会 TLE 。
可以撕烤一下，发现：费用流第一次增广，一定是走某个厨师的倒数 $1$ 时刻（否则不是从源到汇的最短路）。
同样地，如果第 $i$ 个厨师的倒数 $1$ 到 r i r_i ri​ 时刻都满流，那么这次增广一定是选取一个 $i$ ，走第 $i$ 个厨师的倒数 r i + 1 r_i+1 ri​+1 时刻。
所以考虑动态加边：首先，我们只加上菜品到汇点的边、源点到每个厨师倒数 $1$ 时刻的边，以及每个厨师倒数 $1$ 时刻到每个菜品的边。
然后每一次增广，如果增广走的是第 $i$ 个厨师倒数第 $j$ 时刻的边，那么这时候就从源点向第 $i$ 个厨师倒数第 $j+1$ 时刻的点连边，再由第 $i$ 个厨师第 $j+1$ 时刻的点向每个菜品连边。裆燃，如果 j = ∑ i = 1 n p i j=\sum_{i=1}^np_i j=∑i=1n​pi​ 就不要加边。
这样复杂度就有了保证。

Code

#include 
#include 
#include 
#include 
#include 
#include 
#define For(i, a, b) for (i = a; i <= b; i++)
#define Edge(u) for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])
#define CostFlow(e) for (e = pre[T]; e; e = pre[go[e ^ 1]])
using namespace std;inline int read()
{int res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);return bo ? ~res + 1 : res;
}template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}const int R = 45, Z = 105, N = 1e5 + 5, M = 7e6 + 5, INF = 0x3f3f3f3f;
int n, m, p[R], t[R][Z], ecnt = 1, nxt[M], adj[N], go[M],
cap[M], cost[M], dis[N], S, T, tm, pre[N], ans;
bool vis[N];
queue<int> q;void add_edge(int u, int v, int w, int x)
{nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;cap[ecnt] = w; cost[ecnt] = x;nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;cap[ecnt] = 0; cost[ecnt] = -x;
}bool spfa()
{int i;For (i, S, T) dis[i] = INF, vis[i] = 0;dis[S] = 0; q.push(S);while (!q.empty()){int u = q.front(); q.pop(); vis[u] = 0;Edge(u)if (cap[e] && dis[u] + cost[e] < dis[v]){dis[v] = dis[u] + cost[pre[v] = e];if (!vis[v]) vis[v] = 1, q.push(v);}}return dis[T] < INF;
}void jiejuediao()
{int i, e, u = T, fl = INF;CostFlow(e){fl = Min(fl, cap[e]);if (go[pre[u] ^ 1] != S) u = go[pre[u] ^ 1];}CostFlow(e) cap[e] -= fl, cap[e ^ 1] += fl;ans += fl * dis[T];if ((u - 2) % tm + 1 != tm){int x = (u - 1) / tm + 1, y = (u - 1) % tm + 1;add_edge(S, u + 1, 1, 0);For (i, 1, n) add_edge(u + 1, 1 + m * tm + i, 1, y * t[i][x]);}
}int mcmf()
{while (spfa()) jiejuediao();return ans;
}int main()
{int i, j, k;n = read(); m = read();For (i, 1, n) tm += (p[i] = read());For (i, 1, n) For (j, 1, m) t[i][j] = read();S = 1; T = 2 + m * tm + n;For (i, 1, m) For (j, 1, n)add_edge(1 + (i - 1) * tm + 1, 1 + m * tm + j, 1, t[j][i]);For (i, 1, n) add_edge(1 + m * tm + i, T, p[i], 0);For (i, 1, m) add_edge(S, 1 + (i - 1) * tm + 1, 1, 0);cout << mcmf() << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！