题目描述
给定有向图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 个正整数i和j，表示一条有向边(i,j)。
输出格式：
从第1 行开始，每行输出一条路径。文件的最后一行是最少路径数。
输入输出样例
输入样例#1：
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
输出样例#1：
1 4 7 10 11
2 5 8
3 6 9
3
题解
先假设每个点是一条路径，那么现在有n条路径。
然后考虑一些路径的合并，显然合并尽可能多的路径可以最小化路径条数。
然后考虑网络流建模，对于每个点拆成两个，连二分图
对于边<u,v>，连<(u_x,v_y)>，容量为1 。
对于(x)的点，连<(s,x)>，对于(y)，连<(y,t)>，容量都为1，这样可以保证每一个点只连一条边出去，只有一条边连向它。
这样，每条增广路都只经过两个点，可以看成合并两条链。
然后求最大流，答案就是(n-max\_flow).
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
#define maxn 5050
const int inf=2e9;
int n,m,s,t,head[maxn],tot=1,dis[2004],vis[2004],max_flow;
struct edge{int to,nxt,w;}e[maxn<<1];
void add(int u,int v,int w) {e[++tot]=(edge){v,head[u],w},head[u]=tot;}
void ins(int u,int v,int w) {add(u,v,w),add(v,u,0);}
int bfs() {
memset(vis,0,sizeof vis);
memset(dis,63,sizeof dis);
queue<int > q;q.push(s),dis[s]=0,vis[s]=1;
while(!q.empty()) {
int now=q.front();q.pop(),vis[now]=0;
for(int i=head[now];i;i=e[i].nxt)
if(dis[e[i].to]>dis[now]+1&&e[i].w>0) {
dis[e[i].to]=dis[now]+1;
if(!vis[e[i].to]) vis[e[i].to]=1,q.push(e[i].to);
}
}return dis[t]<1e9;
}
int dfs(int x,int f) {
if(x==t) return vis[x]=1,f;
vis[x]=1;int used=0;
for(int i=head[x];i;i=e[i].nxt)
if(!vis[e[i].to]&&e[i].w>0&&dis[e[i].to]==dis[x]+1) {
int d=dfs(e[i].to,min(f-used,e[i].w));
if(d>0) used+=d,e[i].w-=d,e[i^1].w+=d;
if(used==f) break;
}
return used;
}
void dinic() {
while(bfs()) {
vis[t]=1;
while(vis[t]) memset(vis,0,sizeof vis),max_flow+=dfs(s,inf);
}
}
int nxt[maxn],pre[maxn];
int main() {
read(n),read(m);s=0,t=n*2+1;
for(int i=1,x,y;i<=m;i++) read(x),read(y),ins(x,y+n,1);
for(int i=1;i<=n;i++) ins(s,i,1),ins(i+n,t,1);
dinic();
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=e[j].nxt)
if(e[j].to!=s&&e[j].w==0) nxt[i]=e[j].to-n,pre[e[j].to-n]=i;
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++)
if(!vis[i]) {
int now=i;
while(pre[now]) now=pre[now];
while(nxt[now]) printf("%d ",now),vis[now]=1,now=nxt[now];
printf("%d
",now);vis[now]=1;
}
write(n-max_flow);
return 0;
}