最大权闭合子图模板题,具体建模不多说,关键是如何输出两边具体的最小割选取的点集。
一般的 dinic
是直接看所有节点的 dep
,谁大于 0
(或者大于 -1
,具体看怎么实现的)就说明选择了这个点。
对于带有当前弧优化的 ISAP
的话,则 dep
是不会每轮都刷新的。但是我们直接用当前弧的 gap
来统计最后一次推流的第几层出现了断层。也就是看没有任何一个节点使得 dep
为几。找到这个对应的 dep
之后,所有比这个 dep
大的节点就是被选择了的节点。
namespace ISAP
{
using cap = i64;
const int N = 110, M = 5010;
const cap INF = 1145141919;
int n, m, s, t;
cap maxflow;
struct edge
{
int to, nxt;
cap flow;
} e[M << 1];
int h[N];
int cnt;
void init_sz(int _n) { n = _n, m = 0, maxflow = 0, cnt = 1; }
int add_edge(int u, int v, cap flow, bool directed = true)
{
++m;
e[++cnt].to = v, e[cnt].nxt = h[u], e[cnt].flow = flow, h[u] = cnt;
e[++cnt].to = u, e[cnt].nxt = h[v], e[cnt].flow = directed ? 0 : flow, h[v] = cnt;
return cnt;
}
int dep[N], gap[N], cur[N];
std::queue<int> q;
void bfs()
{
memset(dep, 0, sizeof(dep)), memset(gap, 0, sizeof(gap));
q.push(t);
dep[t] = 1, gap[dep[t]] = 1;
while (q.size())
{
int u = q.front();
q.pop();
for (int i = h[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (!dep[v])
q.push(v), dep[v] = dep[u] + 1, ++gap[dep[v]];
}
}
}
cap dfs(int u, cap flow)
{
if (u == t)
return maxflow += flow, flow;
cap vis = 0;
for (int i = cur[u]; i; i = cur[u] = e[i].nxt)
{
int v = e[i].to;
if (e[i].flow && dep[v] + 1 == dep[u])
{
cap d = dfs(v, std::min(flow - vis, e[i].flow));
if (d > 0)
e[i].flow -= d, e[i ^ 1].flow += d, vis += d;
if (vis == flow)
return vis;
}
}
--gap[dep[u]];
if (!gap[dep[u]])
dep[s] = n + 1;
++dep[u], ++gap[dep[u]];
return vis;
}
cap solve(int _s, int _t)
{
maxflow = 0, s = _s, t = _t;
bfs();
while (dep[s] <= n)
memcpy(cur, h, (n + 1) << 2), dfs(s, INF);
return maxflow;
}
}
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0), std::cout.tie(0);
int n, m;
std::string s;
std::getline(std::cin, s);
std::stringstream ss(s);
ss >> n >> m;
int S = n + m + 1, T = n + m + 2;
ISAP::init_sz(T);
i64 full_profit = 0;
int w = 0;
for (int i = 1; i <= n; ++i)
{
std::getline(std::cin, s);
ss = std::stringstream(s);
ss >> w;
ISAP::add_edge(S, i, w), full_profit += w;
while (ss >> w)
ISAP::add_edge(i, n + w, ISAP::INF);
}
for (int i = 1; i <= m; ++i)
std::cin >> w, ISAP::add_edge(n + i, T, w);
i64 ans = full_profit - ISAP::solve(S, T);
int fault_depth = 0;
for (int i = 1; i <= ISAP::n && !fault_depth; ++i)
if (!ISAP::gap[i])
fault_depth = i;
for (int i = 1; i <= n; ++i)
if (ISAP::dep[i] > fault_depth)
std::cout << i << " ";
std::cout << "\n";
for (int i = 1; i <= m; ++i)
if (ISAP::dep[n + i] > fault_depth)
std::cout << i << " ";
std::cout << "\n";
std::cout << ans;
}