Luogu OJ: P2764 Minimum path coverage problem (network flow)

Topic description

Given a directed graph G=(V,E) . Let P be a set of simple paths (disjoint vertices) of G. If every fixed point in V is on exactly one path of P, then P is said to be a path cover of G. The path in P can start from any fixed point of V, and the length is also arbitrary, in particular, it can be 0. The minimum path coverage of G is the path coverage that G contains the fewest paths. Design an efficient algorithm to find the minimum path coverage of a DAG (directed acyclic graph) G.

Hint: Set V={1,2,...,n}, construct the network G1​={V1​,E1​} as follows:

V1​={x0​,x1​,...,xn​}∪{y0​,y1​,...,yn​}

E1​={(x0​,xi​):i∈V}∪{(yi​,y0​):i∈V}∪{(xi​,yj​):(i,j)∈E}

The capacity of each edge is 1, find the (x0​,y0​) maximum flow of the network G1​.

input format

The first line has 2 positive integers n and m. nn is the number of vertices in a given GAP (directed acyclic graph) G, and m is the number of edges in G. The next m lines, each with two positive integers i and j representing a directed edge (i,j).

output format

From line 1, output one path per line. The last line of the file is the minimum number of paths.

Input and output example

Enter #1 to copy

11 12
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
7 10
8 11
9 11
10 11

output #1 copy

1 4 7 10 11
2 5 8
3 6 9
3

Instructions/Tips

1≤n≤150,1≤m≤6000

Contributed by @FlierKing SPJ

Idea: Use network flow to solve the problem of least path coverage. The general way of building a map is to split each point into two points [for example, the label of the point is x, we can split it into x and x+], which are respectively related to the source point and The sinks are connected, as shown in the following figure [source: Huge Zhihu]:

Before drawing:                               

After drawing:

In this figure, we set the edge length of each edge from the source point to the sink point to be 1, and run the maximum flow once to get the maximum number of combined paths, and then subtract the number of points to get the minimum path coverage number. It's almost obvious: every flow from point A to point B' represents a merge. However, only 1 unit of flow is delivered to each point from the source point, which ensures that each point is only passed through once. [Also taken from the above link], for the operation of the output path of this question, you only need to open an additional nxt array, and the starting point x must be the point where edges[x+n][t]=1. [t is the meeting point].

#include<set>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define maxn 550
#define ll long long
#define inf 1e18
int n,m,s,t,lv[maxn],cur[maxn],nxt[maxn];
ll edges[maxn][maxn];
//lv is the number of layers per point
bool bfs(){
	memset(lv,-1,sizeof(lv));
	lv[s]=0;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=1;i<=2*n+1;i++){
			if(edges[now][i]>0 && lv[i]==-1){
				lv[i]=lv[now]+1;
				q.push(i);
			}
		}
	}
	return lv[t]!=-1;
}
ll dfs(int p=s,ll flow=inf){
	if(p==t)
		return flow;
	ll mn=flow;
	for(int i=1;i<=2*n+1;i++){
		if(edges[p][i]>0 && lv[i]==lv[p]+1){
			ll c=dfs(i,min(edges[p][i],mn));
			mn-=c;
			edges[p][i]-=c;
			edges[i][p]+=c;
			if(c && p) nxt[p]=i-n;
		}
	}
	return flow-mn;
}
ll dinic(){
	ll maxFlow=0;
	while(bfs())
		maxFlow+=dfs();
	return maxFlow;
}
int main(void){
	int x,y;
	scanf("%d%d",&n,&m);
	t=2*n+1;
	for(int i=1;i<=n;i++){
		edges[s][i]=1;
		edges[i+n][t]=1;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		edges[x][y+n]=1;
	}
	ll pathNum=n-dinic();
	for(int i=1;i<=n;i++){
		if(edges[i+n][t]){
			int now=i;
			printf("%d",now);
			while(nxt[now]){
				now=nxt[now];
				printf(" %d",now);
			}
			printf("\n");
		}
	}
	printf("%lld\n",pathNum);
	return 0;
}

 

 

Tags: network-flows

Posted by adi on Thu, 05 May 2022 11:50:46 +0300