http://poj.org/problem?id=1422
题目大意：n个点m条有向边，每条边只能走一次，往点上放人让他们走遍所有边，问至少要多少人。
——————————————————————
网上的题解都蛮详尽的了所以不想写这篇博客。
（但是强迫症）
首先这是一道最小路径覆盖问题，有结论转换成求|节点数-最大匹配|，证明看这个人的博客。
我们将每个点拆分成两个点（设左点和右点），左点为一个集合，右点为一个集合。
这样的话两个点ij中间的有向边就是i左点连j右点。
#include<cstdio> #include<cstring> #include<cctype> using namespace std; const int maxn=1001; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)) {w|=ch=='-';ch=getchar();} while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } int n,m,e; bool vis[maxn],a[maxn][maxn]={0}; int shu[maxn]={0}; bool dfs(int i){ for(int j=1;j<=m;j++){ if(a[i][j]&&!vis[j]){ vis[j]=1; if(!shu[j]||dfs(shu[j])){ shu[j]=i; return 1; } } } return 0; } int main(){ int t=read(); while(t--){ memset(a,0,sizeof(a)); memset(shu,0,sizeof(shu)); int ans=0; m=n=read(); e=read(); for(int i=1;i<=e;i++){ int u=read(); int v=read(); if(u>n||v>m) continue; a[u][v]=1; } for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if(dfs(i))ans++; } printf("%d ",n-ans); } return 0; }