网络流24题之 1738: 最小路径覆盖问题
最小路径覆盖问题
模板题，求一个图的最小路径覆盖，输出边数和，路径。不会输出路径的跑dinic然后把图输出来就懂了。
#include <bits/stdc++.h>using namespace std;int k;struct Dinic {static const int MAXN = 30005 + 7;static const int MAXM = 1e7 + 7;static const int INF = 0x3f3f3f3f;int n, m, s, t;int first[MAXN], cur[MAXN], dist[MAXN], sign;struct Node {int to, flow, next;} edge[MAXM];inline void init(int start, int vertex, int ss, int tt) {n = vertex, s = ss, t = tt;for(int i = start; i <= n; i++ ) {first[i] = -1;}sign = 0;}inline void addEdge(int u, int v, int flow) {edge[sign].to = v, edge[sign].flow = flow, edge[sign].next = first[u];first[u] = sign++;}inline void add_edge(int u, int v, int flow) {addEdge(u, v, flow);addEdge(v, u, 0);}int match[MAXN] = {0}, vis[MAXN] = {0};void show_graph() {int cnt = 0;for(int i = 1; i <= k; i++ ) {for(int j = first[i]; ~j; j = edge[j].next) {int to = edge[j].to, w = edge[j].flow;if(to != s && edge[j ^ 1].flow) {match[i] = to - k;}}}for(int i = 1; i <= k; i++ ) {int now = i;if(vis[i]) {continue;}while(1) {printf("%d", now);vis[now] = 1;now = match[now];if(now == 0) {cnt++;puts("");break;} else {printf(" ");}}}printf("%d\n", cnt);}inline int dinic() {int max_flow = 0;while(bfs(s, t)) {for(int i = 0; i <= n; i++ ) {cur[i] = first[i];}max_flow += dfs(s, INF);}return max_flow;}bool bfs(int s, int t) {memset(dist, -1, sizeof(dist));queue<int>que;que.push(s), dist[s] = 0;while(!que.empty()) {int now = que.front();que.pop();if(now == t) {return 1;}for(int i = first[now]; ~i; i = edge[i].next) {int to = edge[i].to, flow = edge[i].flow;if(dist[to] == -1 && flow > 0) {dist[to] = dist[now] + 1;que.push(to);}}}return 0;}int dfs(int now, int max_flow) {if(now == t) {return max_flow;}int ans = 0, next_flow = 0;for(int &i = cur[now]; ~i; i = edge[i].next) {int to = edge[i].to, flow = edge[i].flow;if(dist[to] == dist[now] + 1 && flow > 0) {next_flow = dfs(to, min(max_flow - ans, flow));ans += next_flow;edge[i].flow -= next_flow;edge[i ^ 1].flow += next_flow;if(ans == max_flow) {return max_flow;}}}if(ans == 0) {return dist[now] = 0;}return ans;}} cwl;int main() {int n, m;while(~scanf("%d %d", &n, &m)) {cwl.init(0, 2 * n + 1, 0, 2 * n + 1);for(int i = 1; i <= n; i++ ) {cwl.add_edge(0, i, 1);cwl.add_edge(i + n, 2 * n + 1, 1);}for(int i = 1; i <= m; i++ ) {int u, v;scanf("%d %d", &u, &v);cwl.add_edge(u, v + n, 1);}cwl.dinic();k = n;cwl.show_graph();}return 0;
}