网络流24题-P2764 最小路径覆盖问题

P2764 最小路径覆盖问题

https://www.luogu.com.cn/problem/P2764

题意

给你一个含有n个点的DAG 问你最小有多少条路径(顶点不相交)可以覆盖整个图的所有点

思路

我们先将每个点设为一条路径 然后将每个点拆成两个点 流出点和流入点
让源点根流出点连边 流入点和汇点连边
根据给出的图 建立相应的边 \(u -> v + n\)流量置为1
如果u 和 v 之间有流量流过就说明以u和v为端点的两条路径可以合并
跑最大流 即原n条路径最多可以被合并多少条
n - 最大流即最后的答案
正确性： 应为源点给每个结点都只有1的流量 所以每个结点只能和一条其他路径合并 即这与即使一个点有多个儿子这个点也只能和一个儿子在同一条路径中对应

#include<bits/stdc++.h>
#define ll long long
#define all(a) a.begin(),a.end()
using namespace std;

const int N = 3e5 + 5;
const int M = 1e6 + 1;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;

int n, m;
int s, t, vtot;
int head[N], cur[N];
int dis[N], etot, tot;
int vis[200][200];
vector<int>g[N];
int in[N];
struct edge {
	int v, nxt;
	int f;
}e[M * 2];
//复杂度 O(n^2*m)
//存图用前向星比较方便 有边的信息 
void addedge(int u, int v, int f) {
	//边序号从零开始
	e[etot] = { v, head[u], f }; head[u] = etot++;
	e[etot] = { u, head[v], 0 }; head[v] = etot++;
}

//s到t是否还有路径
bool bfs() {
	for (int i = 1; i <= vtot; i++) {
		dis[i] = 0;
		cur[i] = head[i];
	}
	queue<int>q;
	q.push(s); dis[s] = 1;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; ~i; i = e[i].nxt) {
			//有剩余流量且未被访问过
			if (e[i].f && !dis[e[i].v]) {
				int v = e[i].v;
				dis[v] = dis[u] + 1;
				if (v == t) return true;
				q.push(v);
			}
		}
	}
	return false;
}

//找最优路径
int dfs(int u, int m) {
	if (u == t) return m;
	int flow = 0;
	//cur[]当前弧优化 保证增广过了不再增广
	for (int i = cur[u]; ~i; cur[u] = i = e[i].nxt) {
		//如果流量还有剩余 且该边方向是对的
		if (e[i].f && dis[e[i].v] == dis[u] + 1) {
			int f = dfs(e[i].v, min(m, e[i].f));
			e[i].f -= f;
			e[i ^ 1].f += f;
			m -= f;
			flow += f;
			if (!m) break;//保证复杂度
		}
	}
	if (!flow) dis[u] = -1;
	return flow;
}

int dinic() {
	int flow = 0;
	while (bfs()) flow += dfs(s, INF);
	return flow;
}

void init(int s_, int t_, int vtot_) {
	s = s_;
	t = t_;
	vtot = vtot_;
	for (int i = 1; i <= vtot; i++) head[i] = -1;
}

void dfs(int x) {
	cout << x << " ";
	for (auto to : g[x]) {
		if (!vis[x][to]) {
			dfs(to);
			vis[x][to] = 1;
			break;
		}
	}
}

pair<int, int>E[N];
void solve() {
	cin >> n >> m;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		E[i] = { u, v };
	}

	init(n * 2 + 1, n * 2 + 2, n * 2 + 2);
	for (int i = 1; i <= n; i++) {
		addedge(s, i, 1);
		addedge(i + n, t, 1);
	}

	vector<pair<int, pair<int, int>>>ve;
	for (int i = 1; i <= m; i++) {
		ve.push_back({ etot, E[i] });
		addedge(E[i].first, E[i].second + n, 1);
	}

	ll ans = dinic();
	for (auto x : ve) {
		if (e[x.first].f == 0) {
			g[x.second.first].push_back(x.second.second);
			in[x.second.second]++;
		}
	}

	for (int i = 1; i <= n; i++) {
		if (!in[i]) {
			dfs(i);
			cout << "\n";
		}
	}

	cout << n - ans << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int _t = 1;
    //cin >> _t;
    while (_t--)
        solve();
    return 0;
}