传送门
分层图加网络流,有点像这题
可以证明最多不超过100天,所以才可以分层,不然图的规模会很大。
首先连源点汇点: \((s,1,INF), (n, t, INF)\)
以时间分层,每次把原图中的边 \((u, v, w)\) 改为一条 \((u_{day1}, v_{day2}, w)\) 的弧。
对于 \(u < n\),连一条弧 \((u_{day1}, u_{day2}, INF)\),以及一条 \((n_{day2}, n_{day1}, INF)\)。
然后每次在残量网络上加边增广直至最大流大于等于 \(T\)。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#define rg register
using namespace std;
template < typename T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while (!isdigit(c)) f |= (c == '-'), c = getchar();
while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
s = f ? -s : s;
}
const int _ = 5010;
const int __ = 250010;
const int INF = 2147483647;
int tot = 1, head[_], nxt[__ << 1], ver[__ << 1], cap[__ << 1];
inline void Add_edge(int u, int v, int d)
{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v, cap[tot] = d; }
inline void link(int u, int v, int d) { Add_edge(u, v, d), Add_edge(v, u, 0); }
int n, m, k, s, t, dep[_], cur[_];
struct node { int u, v, d; } x[2452];
inline int id(int u, int d) { return u + (d - 1) * n; }
inline int bfs() {
static queue < int > Q;
memset(dep, 0, sizeof dep);
dep[s] = 1, Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (rg int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (dep[v] == 0 && cap[i] > 0)
dep[v] = dep[u] + 1, Q.push(v);
}
}
return dep[t] > 0;
}
inline int dfs(int u, int flow) {
if (u == t) return flow;
for (rg int& i = cur[u]; i; i = nxt[i]) {
int v = ver[i];
if (dep[v] == dep[u] + 1 && cap[i] > 0) {
int res = dfs(v, min(flow, cap[i]));
if (res) { cap[i] -= res, cap[i ^ 1] += res; return res; }
}
}
return 0;
}
inline int Dinic(int day) {
int res = 0;
while (bfs()) {
cur[s] = head[s], cur[t] = head[t];
for (rg int x = 1; x <= day; ++x)
for (rg int i = 1; i <= n; ++i)
cur[id(i, x)] = head[id(i, x)];
while (int d = dfs(s, INF)) res += d;
}
return res;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
read(n), read(m), read(k);
for (rg int i = 1; i <= m; ++i)
read(x[i].u), read(x[i].v), read(x[i].d);
s = _ - 1, t = _ - 2;
link(s, id(1, 1), INF);
link(id(n, 1), t, INF);
int res = 0;
for (rg int d = 2; ; ++d) {
for (rg int i = 1; i <= m; ++i)
link(id(x[i].u, d - 1), id(x[i].v, d), x[i].d);
for (rg int i = 1; i < n; ++i)
link(id(i, d - 1), id(i, d), INF);
link(id(n, d), id(n, d - 1), INF);
res += Dinic(d);
if (res >= k) { printf("%d\n", d - 1); return 0; }
}
return 0;
}
完结撒花 \(qwq\)
手机扫一扫
移动阅读更方便
你可能感兴趣的文章