题意如题名，最小路径覆盖。
答案为点数减去最大匹配。
用匈牙利直接跑。
#include <cstdio> #include <cstring> #include <vector> using namespace std; const int N=205; int n,m; int map[N][N]; int fr[N]; int vis[N]; int sum; int in[N]; int le; int fa[N]; vector <int > path[N]; int get(int x) { return x==fa[x]?x:fa[x]=get(fa[x]); } void me(int x,int y) { int fx=get(x),fy=get(y); fa[fx]=fy; } bool find(int x) { for (int i=1;i<=n;i++) { if (map[x][i]&&!vis[i]) { vis[i]=1; if (!fr[i]||find(fr[i])) {fr[i]=x;return 1;} } } return 0; } int main() { register int i,j; scanf("%d %d",&n,&m); for (i=1;i<=m;i++) { int x,y; scanf("%d %d",&x,&y); map[x][y]=1; } for (i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if (find(i)) sum++; } //memset(vis,0,sizeof(vis)); for (i=1;i<=n;i++) fa[i]=i; for (i=1;i<=n;i++) { if (fr[i]) if (fa[i]!=fa[fr[i]]) me(i,fr[i]); } for (i=1;i<=n;i++) { path[fa[i]].push_back(i); } for (i=1;i<=n;i++) { if (path[i].size()) { for (j=0;j<path[i].size();j++) { printf("%d ",path[i][j]); } printf("\n"); } } printf("%d",n-sum); }
