原题链接

题目大意

求给定图的最小路径覆盖，并输出对应的路径和路径条数。
最小路径覆盖：
通俗来说就是在一个有向图中,找出最少的路径,使得这些路径经过了所有的点。

解题思路

最小路径覆盖数=|E|-二分图最大匹配数(|E|为有向图的总边数)
将每个点拆为入点和出点，连边(a,b)时由a的入点指向b的出点，再将网络流的源点指向入点，出点指向汇点，跑最大流即可得到二分图最大匹配数。
求解路径：
每条路径的起点与源点间有流量，路径中的点仅与路径上相邻的点有流量

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue> 
#include<vector>
#include<algorithm>
#include<cstring>
#define MAX_V 1000
using namespace std;

const int INF = (unsigned int)(-1)>>1;
struct edge {
	int to,cap,rev;
	bool key; 
};

vector<edge> G[MAX_V]; 
int level[MAX_V]; 
int iter[MAX_V]; 


void add_edge(int from,int to,int cap) {
	G[from].push_back((edge) {
		to,cap,G[to].size(),true
	});
	G[to].push_back((edge) {
		from,0,G[from].size()-1,false
	});
}


void bfs(int s) {
	memset(level,-1,sizeof(level));

	queue<int> que;

	level[s]=0;

	que.push(s);

	while(!que.empty()) {
		int v = que.front();
		que.pop();

		for(int i=0; i<G[v].size(); i++) {
			edge &e = G[v][i];

			if(e.cap > 0 && level[e.to]<0) {
				level[e.to] = level[v] +1;
				que.push(e.to);
			}
		}
	}
}


int dfs(int v,int t,int f) {
	if(v == t)return f;

	for(int &i=iter[v]; i<G[v].size(); i++) {
		edge &e = G[v][i];
		if(e.cap > 0 && level[v] < level[e.to]) {
			int d =dfs(e.to,t,min(f,e.cap));

			if(d>0) {
				e.cap -= d;

				G[e.to][e.rev].cap += d;

				return d;
			}
		}
	}

	return 0;
}


int max_flow(int s, int t) {
	int flow = 0;

	for(;;) {
		bfs(s);

		if(level[t]<0)return flow;
		memset(iter,0,sizeof(iter));

		int f;

		while((f= dfs(s,t,INF))>0) {
			flow += f;
		}
	}
}
int n,m;

void dfs2(int v) 
{
	for(int i=0;i<G[v].size();i++)
	{
		edge e = G[v][i];
		
		if(e.cap == 0 && e.key==true)
		{
			cout<<" "<<e.to-n;
			
			dfs2(e.to-n);
		}
	}
	return;
}



int main()
{
	cin>>n>>m;
	int a,b;
	int s=0,t=2*n+1;
	for(int i=1;i<=n;i++)
	{
		add_edge(s,i,1);
		add_edge(i+n,t,1);
	}
	
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		add_edge(a,b+n,1);
	}	

	int ans = max_flow(s,t);
	
	for(int i=1;i<=n;i++)
	{
		edge &e = G[i+n][0];
		//cout<<i<<":"<<e.cap<<endl;
		if(e.cap == 1 && e.key==true)
		{
			cout<<i;
			dfs2(i);
			cout<<endl;
		}
	}
	
	cout<<n-ans<<endl;
	return 0;
}