套路拆点。
路径覆盖实际上就是一开始全部用单个长度为0的路径覆盖。
然后尽可能多的地合并。
我们拆点成一个二分图，就变成(最小边覆盖问题)了
输出方案画个图就知道了。
上板子
/*
@Date : 2019-07-29 10:41:00
@Author : Adscn (adscn@qq.com)
@Link : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
RG int xi=0;
RG char ch=gc;
bool f=0;
while(ch<'0'||ch>'9')ch=='-'?f=1:f,ch=gc;
while(ch>='0'&&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
if(k<0)k=-k,putchar('-');
if(k>=10)pi(k/10,0);
putchar(k%10+'0');
if(ch)putchar(ch);
}
int n,m;
const int MAXN=150*2+7,MAXM=6000+7+MAXN;
const int S=MAXN-2,T=S+1;
const int inf=2147483647;
struct edge{
int v,nxt,flow;
}e[MAXM<<1|1];
int head[MAXN],cnt;
int cur[MAXN];
int vis[MAXN];
int dep[MAXN];
inline void add(int u,int v,int f){e[++cnt]=(edge){v,head[u],f},head[u]=cnt;}
inline void link(int u,int v,int f){add(u,v,f),add(v,u,0);}
inline void init(void){memset(head,cnt=-1,sizeof head);}
inline bool bfs(void)
{
memset(dep,0,sizeof dep);
static int Q[MAXN],l,r;
dep[Q[l=r=0]=S]=1;
while(l<=r)
for(int p=Q[l++],i=head[p],v;~i;i=e[i].nxt)
if(e[i].flow&&!dep[v=e[i].v])
dep[v]=dep[p]+1,Q[++r]=v;
return dep[T];
}
inline int dfs(int p,int restflow)
{
if(p==T||restflow==0)return restflow;
int sumflow=0;
for(int &i=cur[p],v,flow;(~i)&&restflow;i=e[i].nxt)
if(e[i].flow&&dep[v=e[i].v]==dep[p]+1&&(flow=dfs(v,min(e[i].flow,restflow))))
restflow-=flow,sumflow+=flow,e[i].flow-=flow,e[i^1].flow+=flow;
return sumflow;
}
inline int dinic()
{
int maxflow=0;
while(bfs())memcpy(cur,head,sizeof head),maxflow+=dfs(S,inf);
return maxflow;
}
int main(void)
{
#ifndef ONLINE_JUDGE
// File("");
#endif
init();
n=gi,m=gi;
for(int i=1;i<=m;++i)
{
int u=gi,v=gi;
link(u,v+n,1);
}
for(int i=1;i<=n;++i)link(S,i,1),link(i+n,T,1);
int tmp=dinic();
vis[S]=1;
for(int i=1;i<=n;++i)
if(!vis[i])
{
int t=i;
while(1)
{
pi(t,' ');
vis[t]=1;
bool flag=0;
for(int j=head[t];~j;j=e[j].nxt)
if(!vis[e[j].v]&&!e[j].flow)
{
t=e[j].v;
flag=1;
break;
}
if(!flag)break;
t-=n;
}
putchar('
');
}
pi(n-tmp);
return 0;
}