[HDU 4411] Arrest 强制先后顺序完成全部任务的费用流建模
题目大意
有 $n+1$ 个城市编号 $0\sim n$ 。$0$ 号城市有个警察局,有 $k$ 个警察。他们要去 $1\sim n$ 号城市出警,限制为 : $n$ 个城市都需要恰好被出警过一次,而且必须是按照 $1\sim n$ 的顺序出警 。所有警察执行完对应任务之后,需要再回到 $0$ 号城市。
再给定 $m$ 条双向道路来连接这些城市,保证所有的城市之间是联通的。求所有警察执勤过程中走过的路径总和的最小值。
每个测试点都是多测,注意每组数据的初始化。
Sol.1 费用流
对于一般费用流来说,建模过程可能有点小抽象。不过也算是一个常见套路。
首先跑一次 floyd
最短路,计算两两之间城市最短路。从城市 $i$ 到城市 $j$ 出警的路径长度就从这里得到。
由于所有任务都需要完成,我们可以进行拆点,所有城市 $1\sim n$ 拆成两个点,每个点的左部点到右部点需要连接一个流量为 $1$ ,费用为 -INF
的点(INF
设置的足够大,但是不会大到爆数据精度就行了),这样可以保证所有拆点之间的边都可以被经过。最后的费用答案再加上一个 $n$ 乘以 INF
就行了。
接下来建立超级源点和超级汇点。超级源点向 $0$ 号城市派出所对应的点连一个流量为 $k$ 费用为 $0$ 的边,表示至多可以派出 $k$ 个警察出警。由于这 $k$ 个警察不是必须都要出警,所以再从这个点向超级汇点连一个流量 $k$ 费用 $0$ 的边就行了。然后 $0$ 号城市向刚才 $1\sim n$ 城市的所有左部点都连一个流量为 $1$ 费用为 $dis[0][i]$ 的边,表示至多派一个警察从 $0$ 号城市直接前往 $i$ 号城市执行他的第一个出警任务,首先就要走 $dis[0][i]$ 的路程。再然后从 $1\sim n$ 城市的所有右部点向超级汇点连一个流量为 $1$ 费用为 $dis[0][i]$ 的边,表示其中一个警察在 $i$ 号城市执行完最后一个任务直接回警局,还需要走 $dis[0][i]$ 的路程。
接下来我们再考虑怎么表示所有城市是按照时间顺序先后出警的。那么只要将 $i$ 号城市向所有的 $j$ 号城市 $(j>i)$ 连一个流量为 $1$ 费用为 $dis[i][j]$ 的边就行了,表示其中一个警察是从 $i$ 出警完再到 $j$ 去出警的。
Sol.2 有源汇上下界费用流
有源汇上下界费用流的话,建模思路基本和上面类似。但是“所有任务必须都要完成”这个点的建模思考方式会比普通的费用流简单的多。首先从超级源点到 $0$ 号城市警局的边就可以变成下界是 $0$ 上界是 $k$ 的边,用于表示至多用 $k$ 个警察,但是可以有不用的警察。$0$ 号警局到超级汇点的边就不用连了。
$1\sim n$ 城市的左部点和右部点把流量变成下界 $1$ 上界也是 $1$ ,就能表示这个任务必须执行了。
而其他那些边(从 $0$ 号警局到 $i$ 开始执行任务;从 $i$ 执行完回到 $0$ 号警局;从 $i$ 执行完到 $j$ 执行下一个任务)都是可有可无的,而且都至多经过 $1$ 次。所以改成下界为 $0$ 上界为 $1$ 就行了。
费用流代码
using cap = i64;
const int N = 210;
const int M = 20005;
const int INF = 1919810;
// 1-indexed
namespace MCMF
{
const i64 flow_INF = 1145141919810ll;
const i64 cost_offset = 1145141919810ll;
int n, m, s, t;
struct edge
{
int from, to, nxt;
cap flow, cost;
bool origin;
} e[M << 1];
int cnt;
int h[N];
int add_edge(int u, int v, cap flow, cap cost, bool directed = true)
{
++m;
e[++cnt].from = u, e[cnt].to = v, e[cnt].nxt = h[u], e[cnt].flow = flow, e[cnt].cost = cost, e[cnt].origin = 1;
h[u] = cnt;
e[++cnt].from = v, e[cnt].to = u, e[cnt].nxt = h[v], e[cnt].flow = directed ? 0 : flow, e[cnt].cost = -cost, e[cnt].origin = 0;
h[v] = cnt;
return cnt;
}
cap get_remain_flow(int no) { return e[no].flow; }
int tme;
int vis[N], fa[N], fe[N], circle[N], mark[N];
cap pi[N];
void clr()
{
n = m = s = t = 0, cnt = tme = 1;
memset(h, 0, sizeof(h));
memset(vis, 0, sizeof(vis)), memset(fa, 0, sizeof(fa));
memset(fe, 0, sizeof(fe)), memset(circle, 0, sizeof(circle));
memset(mark, 0, sizeof(mark)), memset(pi, 0, sizeof(pi));
}
void dfs(int u, int fi)
{
fa[u] = e[fi].from, fe[u] = fi;
mark[u] = 1;
for (int i = h[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (e[i].origin && !mark[v])
dfs(v, i);
}
}
cap phi(int u)
{
if (mark[u] == tme)
return pi[u];
mark[u] = tme, pi[u] = phi(fa[u]) + e[fe[u]].cost;
return pi[u];
}
cap pushflow(int eg)
{
int rt = e[eg].from, lca = e[eg].to;
++tme;
int circle_cnt = 0;
while (rt)
mark[rt] = tme, rt = fa[rt];
while (mark[lca] ^ tme)
mark[lca] = tme, lca = fa[lca];
cap minflow = e[eg].flow, p = 2, del_u = 0;
for (int u = e[eg].from; u ^ lca; u = fa[u])
{
circle[++circle_cnt] = fe[u];
if (e[fe[u]].flow < minflow)
minflow = e[fe[u]].flow, del_u = u, p = 0;
}
for (int u = e[eg].to; u ^ lca; u = fa[u])
{
int ne = fe[u] ^ 1;
circle[++circle_cnt] = ne;
if (e[ne].flow < minflow)
minflow = e[ne].flow, del_u = u, p = 1;
}
circle[++circle_cnt] = eg;
cap cost = 0;
for (int i = 1; i <= circle_cnt; ++i)
{
cost += e[circle[i]].cost * minflow;
e[circle[i]].flow -= minflow, e[circle[i] ^ 1].flow += minflow;
}
if (p == 2)
return cost;
int u = e[eg].from, v = e[eg].to;
if (p == 1)
std::swap(u, v);
int last_e = eg ^ p, last_u = v;
while (last_u ^ del_u)
{
last_e ^= 1, --mark[u], std::swap(fe[u], last_e);
int nu = fa[u];
fa[u] = last_u, last_u = u, u = nu;
}
return cost;
}
void init_sz(int _n) { n = _n, m = 0, cnt = 1, tme = 1; }
std::pair<cap, cap> solve(int _s, int _t)
{
s = _s, t = _t;
add_edge(t, s, flow_INF, -cost_offset);
dfs(t, 0), mark[t] = ++tme;
fa[t] = 0;
cap cost = 0, flow = 0;
bool run = 1;
while (run)
{
run = 0;
for (int i = 2; i <= cnt; ++i)
if (e[i].flow && e[i].cost + phi(e[i].from) - phi(e[i].to) < 0)
cost += pushflow(i), run = 1;
}
flow = e[cnt].flow;
return std::make_pair(flow, cost + flow * cost_offset);
}
}
int n, m, k;
int dis[N][N];
void init_dis()
{
for (int i = 0; i <= n; ++i)
memset(dis[i], 0x3f, (n + 1) << 2), dis[i][i] = 0;
}
void floyd()
{
for (int x = 0; x <= n; ++x)
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
dis[i][j] = std::min(dis[i][j], dis[i][x] + dis[x][j]);
}
int main()
{
while (n = rd(), m = rd(), k = rd(), n | m | k)
{
init_dis(), MCMF::clr();
// lowercase s means City 0 start.
int s = (n << 1) | 1, S = s + 1, T = S + 1;
MCMF::init_sz(T);
while (m--)
{
int u = rd(), v = rd(), w = rd();
dis[u][v] = dis[v][u] = std::min(dis[u][v], w);
}
floyd();
// must finish City i before start at City j (i < j)
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
MCMF::add_edge(i + n, j, 1, dis[i][j]);
for (int i = 1; i <= n; ++i)
{
// City 0 to City i
MCMF::add_edge(s, i, 1, dis[0][i]);
// Must arrest at City i
MCMF::add_edge(i, i + n, 1, -INF);
// Finish at City i and return City 0
MCMF::add_edge(i + n, T, 1, dis[0][i]);
}
MCMF::add_edge(S, s, k, 0), MCMF::add_edge(s, T, k, 0);
wr(MCMF::solve(S, T).second + n * INF), putchar('\n');
}
}
有源汇上下界费用流代码
using cap = i64;
const int N = 210;
const int M = 20005;
const int INF = 1919810;
// 1-indexed
namespace MCMF
{
const i64 flow_INF = 1145141919810ll;
const i64 cost_offset = 1145141919810ll;
int n, m, s, t;
struct edge
{
int from, to, nxt;
cap flow, cost;
bool origin;
} e[M << 1];
int cnt;
int h[N];
int add_edge(int u, int v, cap flow, cap cost, bool directed = true)
{
++m;
e[++cnt].from = u, e[cnt].to = v, e[cnt].nxt = h[u], e[cnt].flow = flow, e[cnt].cost = cost, e[cnt].origin = 1;
h[u] = cnt;
e[++cnt].from = v, e[cnt].to = u, e[cnt].nxt = h[v], e[cnt].flow = directed ? 0 : flow, e[cnt].cost = -cost, e[cnt].origin = 0;
h[v] = cnt;
return cnt;
}
cap get_remain_flow(int no) { return e[no].flow; }
int tme;
int vis[N], fa[N], fe[N], circle[N], mark[N];
cap pi[N];
void clr()
{
n = m = s = t = 0, cnt = tme = 1;
memset(h, 0, sizeof(h));
memset(vis, 0, sizeof(vis)), memset(fa, 0, sizeof(fa));
memset(fe, 0, sizeof(fe)), memset(circle, 0, sizeof(circle));
memset(mark, 0, sizeof(mark)), memset(pi, 0, sizeof(pi));
}
void dfs(int u, int fi)
{
fa[u] = e[fi].from, fe[u] = fi;
mark[u] = 1;
for (int i = h[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (e[i].origin && !mark[v])
dfs(v, i);
}
}
cap phi(int u)
{
if (mark[u] == tme)
return pi[u];
mark[u] = tme, pi[u] = phi(fa[u]) + e[fe[u]].cost;
return pi[u];
}
cap pushflow(int eg)
{
int rt = e[eg].from, lca = e[eg].to;
++tme;
int circle_cnt = 0;
while (rt)
mark[rt] = tme, rt = fa[rt];
while (mark[lca] ^ tme)
mark[lca] = tme, lca = fa[lca];
cap minflow = e[eg].flow, p = 2, del_u = 0;
for (int u = e[eg].from; u ^ lca; u = fa[u])
{
circle[++circle_cnt] = fe[u];
if (e[fe[u]].flow < minflow)
minflow = e[fe[u]].flow, del_u = u, p = 0;
}
for (int u = e[eg].to; u ^ lca; u = fa[u])
{
int ne = fe[u] ^ 1;
circle[++circle_cnt] = ne;
if (e[ne].flow < minflow)
minflow = e[ne].flow, del_u = u, p = 1;
}
circle[++circle_cnt] = eg;
cap cost = 0;
for (int i = 1; i <= circle_cnt; ++i)
{
cost += e[circle[i]].cost * minflow;
e[circle[i]].flow -= minflow, e[circle[i] ^ 1].flow += minflow;
}
if (p == 2)
return cost;
int u = e[eg].from, v = e[eg].to;
if (p == 1)
std::swap(u, v);
int last_e = eg ^ p, last_u = v;
while (last_u ^ del_u)
{
last_e ^= 1, --mark[u], std::swap(fe[u], last_e);
int nu = fa[u];
fa[u] = last_u, last_u = u, u = nu;
}
return cost;
}
void init_sz(int _n) { n = _n, m = 0, cnt = 1, tme = 1; }
std::pair<cap, cap> solve(int _s, int _t)
{
s = _s, t = _t;
add_edge(t, s, flow_INF, -cost_offset);
dfs(t, 0), mark[t] = ++tme;
fa[t] = 0;
cap cost = 0, flow = 0;
bool run = 1;
while (run)
{
run = 0;
for (int i = 2; i <= cnt; ++i)
if (e[i].flow && e[i].cost + phi(e[i].from) - phi(e[i].to) < 0)
cost += pushflow(i), run = 1;
}
flow = e[cnt].flow;
return std::make_pair(flow, cost + flow * cost_offset);
}
}
namespace st_bound_MCMF
{
cap fl[N]; // > 0 : supply, < 0 demand
cap supply_sum, base_cost, extra_cost;
int n, s, t, S, T;
void clr()
{
memset(fl, 0, sizeof(fl)), supply_sum = base_cost = extra_cost = 0;
n = s = t = S = T = 0, MCMF::clr();
}
void init(int _n, int _s, int _t) { n = _n, s = _s, t = _t, MCMF::init_sz(n + 2), S = n + 1, T = n + 2; }
void standard_supply_or_demand(int no, cap val) { fl[no] += val; }
void add_edge(int u, int v, cap lo, cap hi, cap cost)
{
fl[u] -= lo, fl[v] += lo;
base_cost += lo * cost;
MCMF::add_edge(u, v, hi - lo, cost);
}
bool solve()
{
MCMF::add_edge(t, s, MCMF::flow_INF, 0);
for (int i = 1; i <= n; ++i)
{
if (fl[i] > 0)
MCMF::add_edge(S, i, fl[i], 0), supply_sum += fl[i];
else if (fl[i] < 0)
MCMF::add_edge(i, T, -fl[i], 0);
}
std::pair<cap, cap> ans = MCMF::solve(S, T);
return extra_cost = ans.second, ans.first == supply_sum;
}
cap mincost() { return base_cost + extra_cost; }
}
int n, m, k;
int dis[N][N];
void init_dis()
{
for (int i = 0; i <= n; ++i)
memset(dis[i], 0x3f, (n + 1) << 2), dis[i][i] = 0;
}
void floyd()
{
for (int x = 0; x <= n; ++x)
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
dis[i][j] = std::min(dis[i][j], dis[i][x] + dis[x][j]);
}
int main()
{
while (n = rd(), m = rd(), k = rd(), n | m | k)
{
init_dis(), st_bound_MCMF::clr();
// lowercase s means City 0 start.
int s = (n << 1) | 1, S = s + 1, T = S + 1;
st_bound_MCMF::init(T, S, T);
while (m--)
{
int u = rd(), v = rd(), w = rd();
dis[u][v] = dis[v][u] = std::min(dis[u][v], w);
}
floyd();
// must finish City i before start at City j (i < j)
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
st_bound_MCMF::add_edge(i + n, j, 0, 1, dis[i][j]);
for (int i = 1; i <= n; ++i)
{
// City 0 to City i
st_bound_MCMF::add_edge(s, i, 0, 1, dis[0][i]);
// Must arrest at City i
st_bound_MCMF::add_edge(i, i + n, 1, 1, 0);
// Finish at City i and return City 0
st_bound_MCMF::add_edge(i + n, T, 0, 1, dis[0][i]);
}
st_bound_MCMF::add_edge(S, s, 0, k, 0);
assert(st_bound_MCMF::solve());
wr(st_bound_MCMF::mincost()), putchar('\n');
}
}