主要思路
这道题原题解作者的思路非常的清晰。我来阐述一下。
首先思考答案的意义,一定是总的权值和减去:
- 变性花费
- 不要的赞助费
- 喝茶费用
我们可以用上面这三个元素组一个网络流,计算最小割使答案最大。
考虑将源点连入雌性,雄性连入雄性,流上限就是变性花费:如果将这种边割掉,那么就是不需要进行变性。考虑朋友的边,如果倾向于变雌性,源点连入,向所有的对应编号连边;如果雄性,连入汇点,所有对应编号的向该朋友连边。
这道题原题解作者的思路非常的清晰。我来阐述一下。
首先思考答案的意义,一定是总的权值和减去:
我们可以用上面这三个元素组一个网络流,计算最小割使答案最大。
考虑将源点连入雌性,雄性连入雄性,流上限就是变性花费:如果将这种边割掉,那么就是不需要进行变性。考虑朋友的边,如果倾向于变雌性,源点连入,向所有的对应编号连边;如果雄性,连入汇点,所有对应编号的向该朋友连边。
在有向图中,有唯一的源地(入度为 0)和汇点(出度为 0),每一条边都有非负的容量,且整张图都会保证平衡状态。这样的图叫做网络流图。
每秒钟每条管道流动的液体最多。常用的算法是 Dinic。先做一次 BFS 划分层次,再用 DFS 来进行流动。Dinic 算法就是在网络图上对残存网络进行利用求得最大流。
其中值得一提的是,Dinic 算法中有一个优化方式可以快速求最大流——当前弧优化。当前弧优化可以在每次找残余网络之前记录遍历到的 head 指针,避免不必要的遍历。
这道题可以看作是网络流的一个模型了。我们把棋盘染色成红色和黑色。然后,源点连红色点,最大流限制为红点的点权;黑点全部连到汇点,最大流限制为黑点的点权。答案为点权总和减去最大流。
我们可以尝试理解一下:对于\(m = 1, n = 2\)的情况:
\[ [ x, y ] \]
那么假设\(x\)为黑点,\(y\)为红点,在网络上是这样的:
我们会发现最大流只会留下较小的一项。这样的话,我们可以感性推广到任何情况,大难点权和减掉最小割就行了。
这个模型有点儿牛逼哦。
我们先来建一个网络。我们把我们得到的\(n\)个点复制一遍,变成第\(i\)与第\(i+n\)个点。让源点全部连接点域\([1,n]\)内的点,让点域\([n+1,2n]\)内的点全部连接汇点。如果有边\((u,v)\),连接边\((u,v+n)\)。这里面所有的边容量都是\(1\)。求最大流做差即可。
我们把网络分层(把它想成 3D 的形状),第一层是源点和原生点,第二层是复制点和汇点。这两层之间的边都相当于有向无环图里的单向边,求最大流即可知道哪些不是路径覆盖中的点。
// LOJ6002.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 200 * 3, INF = 0x3f3f3f3f; int n, m, head[MAX_N], current, upward[MAX_N], s, t, dep[MAX_N], cur[MAX_N], tmpx, tmpy; bool tag[MAX_N]; struct edge { int to, nxt, weight; } edges[6000 << 2]; void addpath(int src, int dst, int weight) { edges[current].to = dst, edges[current].weight = weight; edges[current].nxt = head[src], head[src] = current++; } void add(int src, int dst, int w) { addpath(src, dst, w), addpath(dst, src, 0); } bool bfs() { memset(dep, 0, sizeof(dep)); queue<int> q; q.push(s), dep[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; i != -1; i = edges[i].nxt) if (edges[i].weight > 0 && !dep[edges[i].to]) q.push(edges[i].to), dep[edges[i].to] = dep[u] + 1; } return dep[t] != 0; } int dfs(int u, int flow) { if (u == t || flow == 0) return flow; for (int &i = cur[u]; i != -1; i = edges[i].nxt) if (edges[i].weight > 0 && dep[edges[i].to] == dep[u] + 1) { int to = edges[i].to, fl = dfs(to, min(edges[i].weight, flow)); if (fl > 0) { upward[u] = edges[i].to; if (u != s) tag[edges[i].to - n] = true; edges[i].weight -= fl, edges[i ^ 1].weight += fl; return fl; } } return 0; } int Dinic() { int ans = 0; while (bfs()) { for (int i = 1; i <= 2 * n + 2; i++) cur[i] = head[i]; while (int fl = dfs(s, INF)) ans += fl; } for (int i = 1; i <= n; i++) if (!tag[i]) { int p = i; printf("%d ", p); while (upward[p] && upward[p] != t) printf("%d ", upward[p] - n), p = upward[p] - n; printf("\n"); } return ans; } int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); s = n * 2 + 1, t = s + 1; for (int i = 1; i <= n; i++) add(s, i, 1), add(i + n, t, 1); for (int i = 1; i <= m; i++) { scanf("%d%d", &tmpx, &tmpy); add(tmpx, tmpy + n, 1); } printf("%d", n - Dinic()); return 0; }
一道比较裸的最大流。我们创建源点\(s=0\),让食物从源点连边到每一个牛,牛再创建副本节点(当然主节点和副本节点联通,这样保证只吃一个)连接饮料节点,在连接到汇点。求最大流即可。
// P2891.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 1000, MAX_M = 10000, INF = 0x3f3f3f3f; int head[MAX_N], current, n, f, d, tot, dep[MAX_N], s, t, tmp; struct edge { int to, nxt, weight; } edges[MAX_M << 1]; void addpath(int u, int v, int w) { edges[current].to = v, edges[current].nxt = head[u]; edges[current].weight = w, head[u] = current++; } void add(int u, int v, int w) { addpath(u, v, w), addpath(v, u, 0); } bool bfs() { memset(dep, 0, sizeof(dep)); queue<int> q; q.push(s), dep[s] = 1; do { int u = q.front(); q.pop(); for (int i = head[u]; i != -1; i = edges[i].nxt) if (edges[i].weight > 0 && !dep[edges[i].to]) dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to); } while (!q.empty()); return dep[t] != 0; } int dfs(int u, int flow) { if (u == t || flow == 0) return flow; for (int i = head[u]; i != -1; i = edges[i].nxt) if (dep[edges[i].to] == dep[u] + 1 && edges[i].weight > 0) { int to = edges[i].to; int di = dfs(to, min(flow, edges[i].weight)); if (di > 0) { edges[i].weight -= di, edges[i ^ 1].weight += di; return di; } } return 0; } int dinic() { int ans = 0; while (bfs()) while (int di = dfs(s, INF)) ans += di; return ans; } int main() { memset(head, -1, sizeof(head)); scanf("%d%d%d", &n, &f, &d); s = 0, t = n * 2 + f + d + 1; for (int i = 1; i <= f; i++) add(s, i, 1); for (int i = 1; i <= n; i++) add(i + f, i + f + n, 1); for (int i = 1; i <= d; i++) add(i + 2 * n + f, t, 1); for (int i = 1; i <= n; i++) { int fm, dm; scanf("%d%d", &fm, &dm); while (fm--) scanf("%d", &tmp), add(tmp, i + f, 1); while (dm--) scanf("%d", &tmp), add(f + i + n, tmp + 2 * n + f, 1); } printf("%d", dinic()); return 0; }
类似于之前的 Tarjan 算法,只要\(dfn[u]\leq low[u]\),就可以认为这个点是一个割点。理解:下游的点无法除了通过点 u 的路径到达上游 dfn 更小的点,那么这个就是割点。但是还需要考虑点\(u\)为根节点的情况,因为如果点\(u\)为根的话,那么只要子树大于二就算是一个割点,因为子树间的联通必须需要根节点作为枢纽。
模板题代码:
// P3388.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 20010, MAX_M = 100010; int head[MAX_N], current, n, m, tmpx, tmpy, low[MAX_N], dfn[MAX_N], tot; bool ans[MAX_N]; struct edge { int to, nxt; } edges[MAX_M << 1]; void addpath(int src, int dst) { edges[current].to = dst, edges[current].nxt = head[src]; head[src] = current++; } void tarjan(int u, int fa) { low[u] = dfn[u] = ++tot; int child = 0; for (int i = head[u]; i != -1; i = edges[i].nxt) { if (!dfn[edges[i].to]) { tarjan(edges[i].to, fa), low[u] = min(low[u], low[edges[i].to]); if (low[edges[i].to] >= dfn[u] && u != fa) ans[u] = true; if (u == fa) child++; } low[u] = min(low[u], dfn[edges[i].to]); } if (child >= 2 && u == fa) ans[u] = true; } int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); int cnt = 0; for (int i = 1; i <= m; i++) scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx); for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, i); for (int i = 1; i <= n; i++) if (ans[i]) cnt++; printf("%d\n", cnt); for (int i = 1; i <= n; i++) if (ans[i]) printf("%d ", i); return 0; }
概念:在无向图中,对于点对\(u,v\),在图上删除除\(u,v\)以外的任意一个点,仍然联通,那么称这个点对为点双联通分量。
概念:在无向图中,对于点对\(u,v\),在图上任意删除一条边,\(u,v\)仍连通,则称其为边双连通分量。
https://www.renfei.org/blog/bipartite-matching.html
二分图中,选取最少的点数,使这些点和所有的边都有关联(把所有的边的覆盖),叫做最小点覆盖。
二分图最小点覆盖 = 二分图最大匹配
二分图最大点独立集 = 总点数 – 二分图最大总匹配
例题:[USACO2006NOV]Asteriod,[Usaco2005 jan]Muddy Fields
模板地址:P3386 【模板】二分图匹配
bool dfs(int u, int tm) { for (int i = head[u]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (dfn[to] != tm) { dfn[to] = tm; if ((!match[to]) || dfs(match[to], tm)) { match[to] = u; return true; } } } return false; }
我个人认为这个是相当精妙的一个写法,可以将“继续匹配”和“向上协商”完美的结合在一起,非常的优秀。
此模型可以用于求出多个条件约束下变量的解集。可以通过某些矛盾关系推出可行关系做有向边,Tarjan 染色即可。