这个……学了一条定理
最小路径覆盖=原图总点数-对应二分图最大匹配数
这个对应二分图……是什么呢？
就是这样
这是原图
这是拆点之后对应的二分图。
然后咱们的目标就是从这张图上跑出个最大流来，然后用原图的总点数减去就是答案。
至于记录路径……我发现有一个规律是可以在Dinic跑DFS的时候记。
别的我不知道了。因为我只会Dinic。
代码如下。
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #include<queue> #include<cstdlib> #define maxn 3000 #define maxm 60000 using namespace std; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } inline int count(int i){ return i&1?i+1:i-1; } struct Edge{ int next,to,val; }edge[maxm*5]; int head[maxn*3],num; inline void addedge(int from,int to,int val){ edge[++num]=(Edge){head[from],to,val}; head[from]=num; } inline void add(int from,int to,int val){ addedge(from,to,val); addedge(to,from,0); } bool vis[maxn]; int dfn[maxn]; int list[maxn*3]; int Start,End; int road[maxn*3]; int n,m; bool flag; bool bfs(){ memset(vis,0,sizeof(vis)); queue<int> q; dfn[Start]=1; vis[Start]=1; q.push(Start); while(!q.empty()){ int from=q.front(); q.pop(); for(int i=head[from];i;i=edge[i].next){ int to=edge[i].to; if(vis[to]||edge[i].val<=0) continue; vis[to]=1; dfn[to]=dfn[from]+1; q.push(to); } } return vis[End]; } int dfs(int x,int val){ //printf("%d %d ",x,val); if(val==0||x==End) return val; vis[x]=1; int flow=0; for(int &i=list[x];i;i=edge[i].next){ int to=edge[i].to; if(vis[to]||dfn[to]!=dfn[x]+1||edge[i].val<=0) continue; int now=dfs(to,min(val,edge[i].val)); val-=now; edge[i].val-=now; flow+=now; edge[count(i)].val+=now; if(val<=0){ road[x]=to; break; } } if(flow!=val) dfn[x]=-1; return flow; } int maxflow(){ int ans=0; while(bfs()){ memset(vis,0,sizeof(vis)); for(int i=Start;i<=End;++i) list[i]=head[i]; int now=dfs(Start,0x7fffffff); if(!now) break; ans+=now; } return ans; } int main(){ n=read(),m=read();End=n*2+1; for(int i=1;i<=n;++i){ add(Start,i,1); add(i+n,End,1); } for(int i=1;i<=m;++i){ int from=read(),to=read(); add(from,to+n,1); } int ans=maxflow(); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;++i){ if(road[i]==0) continue; int now=i; while(now!=End&&now){ printf("%d ",now>n?now-=n:now); int x=road[now]; road[now]=0; now=x; } printf(" "); } printf("%d",n-ans); return 0; }