[LOJ#6002]「网络流 24 题」最小路径覆盖

试题描述

给定有向图 G=(V,E)。设 P 是 G 的一个简单路（顶点不相交）的集合。如果 V 中每个顶点恰好在 P 的一条路上，则称 P 是 G 的一个路径覆盖。P 中路径可以从 V 的任何一个顶点开始，长度也是任意的，特别地，可以为 0。G 的最小路径覆盖是 G 的所含路径条数最少的路径覆盖。

设计一个有效算法求一个有向无环图 G 的最小路径覆盖。

输入

第 1 行有 2 个正整数 n 和 m。n 是给定有向无环图 G 的顶点数，m 是 G 的边数。
接下来的 m 行，每行有 2 个正整数 u 和 v，表示一条有向边 (i,j)。

输出

从第 1 行开始，每行输出一条路径。
文件的最后一行是最少路径数。

输入示例

输出示例

数据规模及约定

1≤n≤200,1≤m≤6000

题解

练一下 Dinic 模板。

最小路径覆盖是经典题了。

首先我们假定每个节点都是一个路径，考虑尽量多地合并某两条路径。

不难发现一条路径的贡献可以看成这条路径的节点个数减去边数，并且每个点只能属于一条路径，那么如果把原图上的每个点拆成入和出两个点，那么会发现这个问题转化成了二分图匹配，答案等于原图总点数 - 二分图最大匹配数。

对于所有入点没有被匹配上的点，就是原图中路径的起点，然后沿着这个起点不停地找“出点——入点”的匹配边，找出整个路径。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

using namespace std;

const int BufferSize = 1 << 16;

char buffer[BufferSize], *Head, *Tail;

inline char Getchar() {

	if(Head == Tail) {

		int l = fread(buffer, 1, BufferSize, stdin);

		Tail = (Head = buffer) + l;

	}

	return *Head++;

}

int read() {

	int x = 0, f = 1; char c = Getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }

	return x * f;

}

#define maxn 410

#define maxm 12410

#define oo 2147483647

struct Edge {

	int from, to, flow;

	Edge() {}

	Edge(int _1, int _2, int _3): from(_1), to(_2), flow(_3) {}

} ;

struct Dinic {

	int n, m, s, t, head[maxn], nxt[maxm];

	Edge es[maxm];

	int vis[maxn], Q[maxn], hd, tl;

	int cur[maxn];

	void init() {

		m = 0; memset(head, -1, sizeof(head));

		return ;

	}

	void setn(int _n) {

		n = _n;

		return ;

	}

	void AddEdge(int a, int b, int c) {

		es[m] = Edge(a, b, c); nxt[m] = head[a]; head[a] = m++;

		es[m] = Edge(b, a, 0); nxt[m] = head[b]; head[b] = m++;

		return ;

	}

	bool BFS() {

		memset(vis, 0, sizeof(vis));

		hd = tl = 0; Q[++tl] = s; vis[s] = 1;

		while(hd < tl) {

			int u = Q[++hd];

			for(int i = head[u]; i != -1; i = nxt[i]) {

				Edge& e = es[i];

				if(!vis[e.to] && e.flow) vis[e.to] = vis[u] + 1, Q[++tl] = e.to;

			}

		}

		return vis[t] > 1;

	}

	int DFS(int u, int a) {

		if(u == t || !a) return a;

		int flow = 0, f;

		for(int& i = cur[u]; i != -1; i = nxt[i]) {

			Edge& e = es[i];

			if(vis[e.to] == vis[u] + 1 && (f = DFS(e.to, min(a, e.flow)))) {

				flow += f; a -= f;

				e.flow -= f; es[i^1].flow += f;

				if(!a) return flow;

			}

		}

		return flow;

	}

	int MaxFlow(int _s, int _t) {

		s = _s; t = _t;

		int flow = 0;

		while(BFS()) {

			for(int i = 1; i <= n; i++) cur[i] = head[i];

			flow += DFS(s, oo);

		}

		return flow;

	}

} sol;

int CntP;

struct Point {

	int id;

	Point(): id(0) {}

	int p() { return id ? id : id = ++CntP; }

} inu[maxn], outu[maxn], S, T;

int tmp[maxn], cntt, uid[maxn];

int main() {

	int n = read(), m = read();

	sol.init(); S.p(); T.p();

	for(int i = 1; i <= n; i++)

		sol.AddEdge(S.p(), outu[i].p(), 1), uid[outu[i].p()] = i,

		sol.AddEdge(inu[i].p(), T.p(), 1), uid[inu[i].p()] = i;

	for(int i = 1; i <= m; i++) {

		int a = read(), b = read();

		sol.AddEdge(outu[a].p(), inu[b].p(), 1);

	}

	sol.setn(CntP);

	int ans = n - sol.MaxFlow(S.p(), T.p());

	for(int i = 1; i <= n; i++) {

		bool iss = 0;

		for(int t = sol.head[inu[i].p()]; t != -1; t = sol.nxt[t]) {

			Edge& e = sol.es[t];

			if(e.to == T.p() && e.flow){ iss = 1; break; }

		}

		if(!iss) continue;

		int node = i; cntt = 0; tmp[++cntt] = node;

		for(;;) {

			bool has = 0;

			for(int t = sol.head[outu[node].p()]; t != -1; t = sol.nxt[t]) {

				Edge& e = sol.es[t];

				if(e.to != S.p() && !e.flow){ has = 1; tmp[++cntt] = node = uid[e.to]; break; }

			}

			if(!has) break;

		}

		for(int i = 1; i <= cntt; i++) printf("%d%c", tmp[i], i < cntt ? ' ' : '\n');

	}

	printf("%d\n", ans);

	return 0;

}

巴特西

[LOJ#6002]「网络流 24 题」最小路径覆盖

最新文章

热门文章