Solution to 网络流 24 题。
Day 1：1st - 6th
A. 星际转移问题
http://222.180.160.110:61235/contest/3952/problem/1
如果就按照题目给的路线图，我们显然无法考虑到飞船到达的时刻。同时 \(n\) 和 \(m\) 又很小，我们就知道了，「人不能两次踏进同一条河流」，\(1\) 时刻的站 \(p\) 和 \(2\) 时刻的站 \(p\) 也不能是同一个站 \(p\)。
考虑用 \((p, t)\) 表示 \(t\) 时刻的站 \(p\)，然后对于每条路线跑个暴力连边，容量全部为 \(H_i\)。
怎么控制时间最小呢？二分一下就可以了…… 然后最大流判定是不是满流的即可。
以及注意到对于同一站点，前面的时刻可以留下来等后面的时刻，我们将同一站的前一时刻和后一时刻全部连边，容量为 \(k\)。以及保留节目对源点拆点以控制流量为 \(k\)。
经实验答案最大为 29，所以把二分上界设为 30 即可
理论上来说答案可能很大，比如你谷最后一组数据的答案就是 \(900\)
多，所以我掐指一算用天才般的算术技巧开了 \(10^4\)。真的，数数位天才就是我。
woc，这题居然没人做，果然我还是太强了。
为什么都跑去做 T4 了，这个不是按难度顺序排列的吗？
哦哦，好像不是，那（Na）没（Mei）事（Shi）了（Le）。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int lim = 1e4;
const int inf = 1e18;
const int maxm = 4e5 + 5;
const int maxn = 5e4 + 15;
struct _ {
int v, w, n;
_() {}
_(int v1, int w1, int n1) {
v = v1, w = w1, n = n1;
}
};
struct __ {
int c;
std::vector<int> p;
};
_ u[maxm];
__ w[maxn];
int h[maxn];
int l, mid, r;
int gs, gt, tot = 1;
int n, m, k, s, mt, x, res, y;
int vis[maxn], now[maxn], dep[maxn];
int min(int x, int y) { return x < y ? x : y; }
int fun(int p, int t) { return (p - 1) * mt + t; }
bool BFS(int n) {
std::fill(vis + 1, vis + n + 1, 0);
std::fill(dep + 1, dep + n + 1, 0);
std::queue<int> q;
dep[gs] = 1, vis[gs] = 1;
q.push(gs), now[gs] = h[gs];
while (!q.empty()) {
int f = q.front(); q.pop();
for (int i = h[f]; i; i = u[i].n) {
int v = u[i].v, w = u[i].w;
if (vis[v] == 1 || w == 0) continue;
vis[v] = 1, now[v] = h[v];
dep[v] = dep[f] + 1, q.push(v);
if (v == gt) return 1;
}
}
return 0;
}
int findP(int x, int flow = inf) {
if (x == gt) return flow;
int rest = flow, i;
for (i = now[x]; rest && i; i = u[i].n) {
int v = u[i].v, w = u[i].w;
now[x] = i;
if (dep[v] != dep[x] + 1 || w == 0)
continue;
int t = findP(v, min(rest, w));
if (t == 0) dep[v] = 0;
rest -= t, u[i].w -= t, u[i ^ 1].w += t;
}
return flow - rest;
}
int Dinic(int n) {
int res = 0;
while (BFS(n)) {
int t = findP(gs);
while (t) res += t, t = findP(gs);
}
return res;
}
void add(int x, int y, int w) {
u[++tot] = _(y, w, h[x]);
h[x] = tot;
return;
}
void addf(int x, int y, int w) {
add(x, y, w), add(y, x, 0);
return;
}
void Init(void) {
tot = 1;
memset(h, 0, sizeof (h));
return;
}
bool check(int x) {
Init();
mt = x, s = fun(n, mt) + 1;
gs = s + 1, gt = s + 2;
addf(gs, s, k);
for (int i = 1; i <= mt; ++i) {
addf(s, fun(n - 1, i), k);
addf(fun(n, i), gt, k);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < mt; ++j)
addf(fun(i, j), fun(i, j + 1), k);
}
for (int i = 1; i <= m; ++i) {
int p = 0, x = 0, la = 0;
while (++p <= mt) {
if (la != 0)
addf(fun(la, p - 1), fun(w[i].p[x], p), w[i].c);
la = w[i].p[x];
if (++x >= w[i].p.size()) x = 0;
}
}
return (Dinic(gt) == k);
}
int main() {
read(n), read(m), read(k);
for (int i = 1; i <= m; ++i) {
read(w[i].c), read(y);
while (y--) {
read(x);
if (x == 0) x = n + 1;
else if (x == -1) x = n + 2;
w[i].p.push_back(x);
}
}
n += 2;
l = 1, r = lim;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid))
res = mid, r = mid - 1;
else l = mid + 1;
}
print(res ? res - 1 : 0, '\n');
return 0;
}
} // namespace XSC062
#undef intB. 最长递增子序列
http://222.180.160.110:61235/contest/3952/problem/2
就算知道不是按难度顺序排列我也要顺序开题。欸嘿，就是玩。
第一问很水，跑个 DP 就行。
第二问有点意思，取出就代表只能选一次，总之典中典，把每个数拆成入点和出点，容量为 \(1\)，这样就可以只选一次了。
那怎么保证每次找到的流一定是 LIS 呢？其实这和我们 Dinic 的深度分层数组有异曲同工之妙，我们把 \(f_i = f_j + 1(i>j,A_i\ge A_j)\) 的 \((j, i)\) 连边，容量为 \(1\) 即可。
然后源点只和满足 \(f_x = 1\) 的 \(x\) 连边，相应地，汇点之和满足 \(f_x = \text{LIS}\) 的 \(x\) 连边。
第三问很好想啊，我们把 \(1\) 到源点和 \(n\) 到汇点的容量设成无穷大就好。
然后踩了半天的坑，这道题的拆点部分不知道为什么必须要连双向边。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int inf = 1e18;
const int maxm = 4e5 + 5;
const int maxn = 5e5 + 15;
struct _ {
int v, w, n;
_() {}
_(int v1, int w1, int n1) {
v = v1, w = w1, n = n1;
}
};
_ u[maxm];
int n, res;
int gs, gt, tot = 1;
int a[maxn], h[maxn], f[maxn];
int vis[maxn], now[maxn], dep[maxn];
int min(int x, int y) { return x < y ? x : y; }
int max(int x, int y) { return x > y ? x : y; }
bool BFS(int n) {
std::fill(vis + 1, vis + n + 1, 0);
std::fill(dep + 1, dep + n + 1, 0);
std::queue<int> q;
dep[gs] = 1, vis[gs] = 1;
q.push(gs), now[gs] = h[gs];
while (!q.empty()) {
int f = q.front(); q.pop();
for (int i = h[f]; i; i = u[i].n) {
int v = u[i].v, w = u[i].w;
if (vis[v] == 1 || w == 0) continue;
vis[v] = 1, now[v] = h[v];
dep[v] = dep[f] + 1, q.push(v);
if (v == gt) return 1;
}
}
return 0;
}
int findP(int x, int flow = inf) {
if (x == gt) return flow;
int rest = flow, i;
for (i = now[x]; rest && i; i = u[i].n) {
int v = u[i].v, w = u[i].w;
now[x] = i;
if (dep[v] != dep[x] + 1 || w == 0) continue;
int t = findP(v, min(rest, w));
if (t == 0) dep[v] = 0;
rest -= t, u[i].w -= t, u[i ^ 1].w += t;
}
return flow - rest;
}
int Dinic(int n) {
int res = 0;
while (BFS(n)) {
int t = findP(gs);
while (t) res += t, t = findP(gs);
}
return res;
}
void add(int x, int y, int w) {
u[++tot] = _(y, w, h[x]);
h[x] = tot;
return;
}
void addf(int x, int y, int w) {
add(x, y, w), add(y, x, 0);
return;
}
int main() {
read(n);
gs = 2 * n + 1, gt = gs + 1;
for (int i = 1; i <= n; ++i) {
read(a[i]), f[i] = 1;
addf(i, i + n, 1);
addf(i + n, i, 1);
for (int j = 1; j < i; ++j) {
if (a[j] <= a[i])
f[i] = max(f[i], f[j] + 1);
}
res = max(res, f[i]);
for (int j = 1; j < i; ++j) {
if (a[j] <= a[i] && f[i] == f[j] + 1)
addf(j, i + n, 1);
}
}
for (int i = 1; i <= n; ++i) {
if (f[i] == 1) addf(gs, i, 1);
if (f[i] == res) addf(i + n, gt, 1);
}
print(res, '\n');
print(Dinic(gt), '\n');
tot = 1;
memset(h, 0, sizeof (h));
for (int i = 1; i <= n; ++i) {
addf(i, i + n, 1);
addf(i + n, i, 1);
for (int j = 1; j < i; ++j) {
if (a[j] <= a[i] && f[i] == f[j] + 1)
addf(j, i + n, 1);
}
}
for (int i = 1; i <= n; ++i) {
if (f[i] == 1) {
if (i == 1) addf(gs, i, inf);
else addf(gs, i, 1);
}
if (f[i] == res) {
if (i == n) addf(i + n, gt, inf);
else addf(i + n, gt, 1);
}
}
print(Dinic(gt), '\n');
return 0;
}
} // namespace XSC062
#undef intC. 餐巾计划问题
http://222.180.160.110:61235/contest/3952/problem/3
这个有点简单啊。就差把费用流三个大字拍你脸上了。
用过和没用过的餐巾是不能混合处理的，故考虑拆点，把每一天拆出来一个点表示当天所有用过的餐巾量（注意不止是当天用过的，还可以是前几天传下来的）。
首先不难想到大源点和每天的没用过连边，容量为无穷大，费用为购买费用，表示购买餐巾；用过的和下一天用过的连边，容量为无穷大，费用为 \(0\)，表示用过的餐巾的继承；用过的和快洗 / 慢洗所需时间后的没用过的连边，容量为无穷大，费用为快洗 / 慢洗费用，表示把用过的洗成没用过的（奇奇怪怪）。
那么问题来了，怎么表示使用餐巾呢？这里有一个很妙的处理方式，把没用过的朝大汇点连边，容量为当天使用量，费用为 \(0\)，表示把这么多没用过的餐巾销毁；再把大源点朝用过的连边，容量也为当天使用量，费用为 \(0\)，表示凭空变出来这么多条用过的餐巾。
然后跑个费用流就可以了。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int inf = 1e18;
const int maxn = 4e3 + 5;
const int maxm = 6e5 + 5;
struct _ {
int v, c, w, n;
_() {}
_(int v1, int c1, int w1, int n1) {
v = v1, c = c1, w = w1, n = n1;
}
};
_ u[maxm];
bool inq[maxn];
int gs, gt, tot = 1;
int h[maxn], dis[maxn];
int fl[maxn], pre[maxn];
int n, m, t1, c1, t2, c2, res, x;
int min(int x, int y) { return x < y ? x : y; }
bool SPFA(int s, int n) {
std::queue<int> q;
std::fill(dis + 1, dis + n + 1, inf);
q.push(s), dis[s] = 0, inq[s] = 1;
pre[s] = inf, pre[gt] = 0, fl[s] = inf;
while (!q.empty()) {
int f = q.front();
q.pop(), inq[f] = 0;
for (int i = h[f]; i; i = u[i].n) {
if (u[i].c == 0) continue;
int v = u[i].v, w = u[i].w;
if (dis[v] > dis[f] + w) {
pre[v] = i ^ 1;
dis[v] = dis[f] + w;
fl[v] = min(fl[f], u[i].c);
if (!inq[v]) inq[v] = 1, q.push(v);
}
}
}
return pre[gt];
}
void SSP(int s, int n) {
int p, mn, d;
while (SPFA(s, n)) {
mn = fl[gt], d = 0;
for (p = gt; p != s; p = u[pre[p]].v) {
u[pre[p]].c += mn;
u[pre[p] ^ 1].c -= mn;
d += u[pre[p] ^ 1].w;
}
res += mn * d;
}
return;
}
void add(int x, int y, int c, int w) {
u[++tot] = _(y, c, w, h[x]);
h[x] = tot;
return;
}
void addf(int x, int y, int c, int w) {
add(x, y, c, w), add(y, x, 0, -w);
return;
}
int main() {
read(n);
gs = 2 * n + 1, gt = gs + 1;
for (int i = 1; i <= n; ++i) {
read(x);
addf(i, gt, x, 0);
addf(gs, i + n, x, 0);
if (i != n)
addf(i + n, i + 1 + n, inf, 0);
}
read(m), read(t1);
read(c1), read(t2), read(c2);
for (int i = 1; i <= n; ++i) {
addf(gs, i, inf, m);
if (i + t1 <= n)
addf(i + n, i + t1, inf, c1);
if (i + t2 <= n)
addf(i + n, i + t2, inf, c2);
}
SSP(gs, gt);
print(res, '\n');
return 0;
}
} // namespace XSC062
#undef intD. 运输问题
http://222.180.160.110:61235/contest/3952/problem/4
不是很理解啊，这题就一个普普通通的二分图建模，有什么难点吗，，，
哦，蓝的，那没事了。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int inf = 1e18;
const int maxn = 4e3 + 5;
const int maxm = 6e5 + 5;
struct _ {
int v, c, w, n;
_() {}
_(int v1, int c1, int w1, int n1) {
v = v1, c = c1, w = w1, n = n1;
}
};
bool inq[maxn];
int gs, gt, tot = 1;
_ u[maxm], u1[maxm];
int fl[maxn], pre[maxn];
int h[maxn], dis[maxn], h1[maxn];
int n, m, t1, c1, t2, c2, res, x;
int min(int x, int y) {
return x < y ? x : y;
}
bool SPFA(int s, int n) {
std::queue<int> q;
std::fill(dis + 1, dis + n + 1, inf);
q.push(s), dis[s] = 0, inq[s] = 1;
pre[s] = inf, pre[gt] = 0, fl[s] = inf;
while (!q.empty()) {
int f = q.front();
q.pop(), inq[f] = 0;
for (int i = h[f]; i; i = u[i].n) {
if (u[i].c == 0)
continue;
int v = u[i].v, w = u[i].w;
if (dis[v] > dis[f] + w) {
pre[v] = i ^ 1;
dis[v] = dis[f] + w;
fl[v] = min(fl[f], u[i].c);
if (!inq[v]) inq[v] = 1, q.push(v);
}
}
}
return pre[gt];
}
bool SPFA1(int s, int n) {
std::queue<int> q;
std::fill(pre + 1, pre + n + 1, 0);
std::fill(dis + 1, dis + n + 1, -inf);
q.push(s), dis[s] = 0, inq[s] = 1;
pre[s] = inf, pre[gt] = 0, fl[s] = inf;
while (!q.empty()) {
int f = q.front();
q.pop(), inq[f] = 0;
for (int i = h[f]; i; i = u[i].n) {
if (u[i].c == 0) continue;
int v = u[i].v, w = u[i].w;
if (dis[v] < dis[f] + w) {
pre[v] = i ^ 1;
dis[v] = dis[f] + w;
fl[v] = min(fl[f], u[i].c);
if (!inq[v])
inq[v] = 1, q.push(v);
}
}
}
return pre[gt];
}
void SSP(int s, int n) {
int p, mn, d;
while (SPFA(s, n)) {
mn = fl[gt], d = 0;
for (p = gt; p != s; p = u[pre[p]].v) {
u[pre[p]].c += mn;
u[pre[p] ^ 1].c -= mn;
d += u[pre[p] ^ 1].w;
}
res += mn * d;
}
return;
}
void SSP1(int s, int n) {
int p, mn, d;
while (SPFA1(s, n)) {
mn = fl[gt], d = 0;
for (p = gt; p != s; p = u[pre[p]].v) {
u[pre[p]].c += mn;
u[pre[p] ^ 1].c -= mn;
d += u[pre[p] ^ 1].w;
}
res += mn * d;
}
return;
}
void add(int x, int y, int c, int w) {
u[++tot] = _(y, c, w, h[x]);
h[x] = tot;
return;
}
void addf(int x, int y, int c, int w) {
add(x, y, c, w), add(y, x, 0, -w);
return;
}
int main() {
read(n), read(m);
gs = n + m + 1, gt = gs + 1;
for (int i = 1; i <= n; ++i)
read(x), addf(gs, i, x, 0);
for (int i = 1; i <= m; ++i)
read(x), addf(i + n, gt, x, 0);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
read(x), addf(i, j + n, inf, x);
}
memcpy(h1, h, sizeof (h1));
memcpy(u1, u, sizeof (u1));
SSP(gs, gt);
print(res, '\n'), res = 0;
memcpy(h, h1, sizeof (h));
memcpy(u, u1, sizeof (u));
SSP1(gs, gt);
print(res, '\n');
return 0;
}
} // namespace XSC062
#undef intE. 最小路径覆盖
http://222.180.160.110:61235/contest/3952/problem/5
当我们把所有点视作长度为 \(0\) 的路径时，答案为 \(n\)。怎么让这个答案减小呢？我们需要 合并路径。
假设有路径 \(u \to x\) 和 \(x \to v\)，那么将它们合并为 \(u\to v\) 显然可以得到更优的答案。
那么这个时候就有同学要问了，我选择合并路径的方式会不会对答案产生影响呢？这个不急，我们讲完了再证明。
首先开一个新图，把所有点整一个保留节目，\(S\to x\) 建一条容量为 \(1\) 的边；\(x' \to T\) 建一条容量为 \(1\) 的边；对于边 \(u\to v\)，在 \(u\to v'\) 建一条容量为 \(1\) 的边。
这个时候我们就有了一个类二分图的模型。想想看，我们在里面跑出来的最大流是什么？
在这种容量均为 \(1\) 的类二分图模型中，网络流中找到的路径其实就是二分图中的增广路，因为反向的容量为 \(0\) 的边就相当于已匹配边，会限制搜索进一步搜下去。
在二分图中，每找到一条增广路，最大匹配的大小便扩大 \(1\)；在这里的网络流中也一样，每找到一条路径，最大流的大小便扩大 \(1\)。
那么，这里的「路径」究竟有什么含义？
一条从 \(S\) 到 \(T\) 的边，若其流量为 \(1\)，我们将它视作原图中被选中、加入路径集合的边，你会发现，找最大流（不断延长路径）的过程就相当于在合并路径，而且最后这个新图满足：点和边都不会被重复选中，且因为我们找的是最大流，所有点都会被选中。
好好好，正确性就很显而易见了，来自于二分图增广路找最大匹配的正确性（被打）。
那么求出最大流 \(f\)，因为每合并一次路径，路径的条数就会减少 \(1\)，所以最后的答案就是 \(N - f\)。方案呢？
因为网络流特性，你会发现路径的起点一定是 \(S\to x\)（废话），所以找出所有 \(S\to x\) 流量为 \(1\) 的 \(x\)，它们就是每条路径的起点。
因为路径没有交叉且肯定联通，所以你沿着这个起点一直找流量为 \(1\) 的边就能找到头。
namespace XSC062 {
using namespace fastIO;
const int inf = 1e18;
const int maxn = 4e3 + 5;
const int maxm = 6e5 + 5;
struct _ {
int v, w, n;
_() {}
_(int v1, int w1, int n1) {
v = v1, w = w1, n = n1;
}
};
_ u[maxm];
bool vis1[maxn];
int n, m, x, y, res;
int gs, gt, tot = 1;
int a[maxn], h[maxn], f[maxn];
int vis[maxn], now[maxn], dep[maxn];
int min(int x, int y) { return x < y ? x : y; }
int max(int x, int y) { return x > y ? x : y; }
bool BFS(int n) {
std::fill(vis + 1, vis + n + 1, 0);
std::fill(dep + 1, dep + n + 1, 0);
std::queue<int> q;
dep[gs] = 1, vis[gs] = 1;
q.push(gs), now[gs] = h[gs];
while (!q.empty()) {
int f = q.front(); q.pop();
for (int i = h[f]; i; i = u[i].n) {
int v = u[i].v, w = u[i].w;
if (vis[v] == 1 || w == 0) continue;
vis[v] = 1, now[v] = h[v];
dep[v] = dep[f] + 1, q.push(v);
if (v == gt) return 1;
}
}
return 0;
}
int findP(int x, int flow = inf) {
if (x == gt) return flow;
int rest = flow, i;
for (i = now[x]; rest && i; i = u[i].n) {
int v = u[i].v, w = u[i].w;
now[x] = i;
if (dep[v] != dep[x] + 1 || w == 0) continue;
int t = findP(v, min(rest, w));
if (t == 0) dep[v] = 0;
rest -= t, u[i].w -= t, u[i ^ 1].w += t;
}
return flow - rest;
}
int Dinic(int n) {
int res = 0;
while (BFS(n)) {
int t = findP(gs);
while (t) res += t, t = findP(gs);
}
return res;
}
void add(int x, int y, int w) {
u[++tot] = _(y, w, h[x]);
h[x] = tot;
return;
}
void addf(int x, int y, int w) {
add(x, y, w), add(y, x, 0);
return;
}
void output(int x) {
if (x == gs) return;
print(x, ' '), vis1[x] = 1;
for (int i = h[x]; i; i = u[i].n) {
int v = u[i].v;
if (v <= n || v > 2 * n || vis1[v - n])
continue;
if (u[i].w == 0) {
output(u[i].v - n);
return;
}
}
return;
}
int main() {
read(n), read(m);
gs = 2 * n + 1, gt = gs + 1;
for (int i = 1; i <= n; ++i) {
addf(gs, i, 1);
addf(i + n, gt, 1);
}
while (m--) {
read(x), read(y);
addf(x, y + n, 1);
}
res = n - Dinic(gt);
for (int i = h[gt]; i; i = u[i].n) {
if (u[i ^ 1].w == 1) {
output(u[i].v - n);
putchar('\n');
}
}
print(res, '\n');
return 0;
}
} // namespace XSC062
#undef intF. 数字梯形
http://222.180.160.110:61235/contest/3952/problem/6
在 GM 的强制要求下只能跳了，呜呜呜
Day 2：7th - 14th
A. 太空飞行计划
http://222.180.160.110:61235/contest/3976/problem/1
不难想到把大源点和实验连容量为报酬的边；把仪器和大汇点连容量为消费的边；实验和仪器之间连容量为无穷大的边。
这个时候我们要选择一些实验不去做，选择一些仪器不要，并且要求要和不要的实验和仪器之间不能有边关联，还要求留下的利润最大。
假如我们把删去一条仪器边视作保留仪器，删去一条实验边视作跳过实验，这是什么？最小割！因为必须保证没有关联，这和最小割要求被分为两个部分是符合的。因为中间的边容量无穷大，故绝对不会选中间的边。同时，它删除了最不赚钱的实验，保留了最便宜的仪器。
据说这也是个经典最小割模型，建议掌握。
然后答案呢？先暂时将器材视为负权值，则：
- 总收入 为 被选中的实验权值 加上 被选中的器材权值
- 被选中的实验权值 为 所有实验权值和 减去 未被选择的实验权值和
- 总收入 为 所有实验权值和 减去 未被选择的实验权值和 加上 被选中的器材权值
- 总收入 为 所有实验权值和 减去 未被选择的实验权值和 减去 被选中的器材权值的相反数
- 最小割 为 未被选择的实验权值和 加上 被选中的器材权值的相反数
- 总收入 为 被选中的实验权值 减去 最小割
那么怎么输出方案呢？
https://www.luogu.com.cn/blog/35891/solution-p2762
woc 这篇讲得太好了。最后一次 Dinic 失败了，这是为什么呢？因为 BFS 找不到汇点了，说明若干条残量为 0 的边已经堵死了从源点到汇点的路。这个时候这些残量为 0 的边其实就是最小割。
那选取的实验和仪器，就是从源点出发可以到达的（已在 BFS 中为其分层作为记号），所以只需统计有层数的点即可。太妙了。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int inf = 1e18;
const int maxn = 4e3 + 5;
const int maxm = 6e5 + 5;
struct _ {
int v, w, n;
_() {}
_(int v1, int w1, int n1) {
v = v1, w = w1, n = n1;
}
};
_ u[maxm];
bool vis1[maxn];
int n, m, x, y, res;
int gs, gt, tot = 1;
int a[maxn], h[maxn], f[maxn];
int vis[maxn], now[maxn], dep[maxn];
int min(int x, int y) { return x < y ? x : y; }
int max(int x, int y) { return x > y ? x : y; }
bool BFS(int n) {
std::fill(vis + 1, vis + n + 1, 0);
std::fill(dep + 1, dep + n + 1, 0);
std::queue<int> q;
dep[gs] = 1, vis[gs] = 1;
q.push(gs), now[gs] = h[gs];
while (!q.empty()) {
int f = q.front(); q.pop();
for (int i = h[f]; i; i = u[i].n) {
int v = u[i].v, w = u[i].w;
if (vis[v] == 1 || w == 0) continue;
vis[v] = 1, now[v] = h[v];
dep[v] = dep[f] + 1, q.push(v);
if (v == gt) return 1;
}
}
return 0;
}
int findP(int x, int flow = inf) {
if (x == gt) return flow;
int rest = flow, i;
for (i = now[x]; rest && i; i = u[i].n) {
int v = u[i].v, w = u[i].w;
now[x] = i;
if (dep[v] != dep[x] + 1 || w == 0) continue;
int t = findP(v, min(rest, w));
if (t == 0) dep[v] = 0;
rest -= t, u[i].w -= t, u[i ^ 1].w += t;
}
return flow - rest;
}
int Dinic(int n) {
int res = 0;
while (BFS(n)) {
int t = findP(gs);
while (t) res += t, t = findP(gs);
}
return res;
}
void add(int x, int y, int w) {
u[++tot] = _(y, w, h[x]);
h[x] = tot;
return;
}
void addf(int x, int y, int w) {
add(x, y, w), add(y, x, 0);
return;
}
int main() {
scanf("%lld %lld", &n, &m);
gs = n + m + 1, gt = gs + 1;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &x);
addf(gs, i, x);
res += x;
std::string tmp;
std::getline(std::cin, tmp);
std::stringstream t(tmp);
while (t >> y)
addf(i, y + n, inf);
}
for (int i = 1; i <= m; ++i)
read(x), addf(n + i, gt, x);
res -= Dinic(gt);
for (int i = 1; i <= n; ++i)
if (dep[i] != 0) print(i, ' ');
putchar('\n');
for (int i = n + 1; i <= n + m; ++i)
if (dep[i] != 0) print(i - n, ' ');
putchar('\n'), print(res, '\n');
return 0;
}
} // namespace XSC062
#undef int