题意：求有向图的最小路径覆盖，但是点可以被多条路径重复走过！
求最小路径覆盖的问题：HDU1151, 链接: http://acm.hdu.edu.cn/showproblem.php?pid=1151
分析：点能被重复覆盖是和单纯地求最小路径覆盖的区别，这样的话在一个弱连通子图中，可能出现中间结点已经被走过，但是之后的点没被覆盖的情况，这时匹配的结果就会比原来大。
那么可以通过求出图的传递闭包来加边，将原来没有直接边的点建立关系，这样就能得到正确结果。
#include#include #include #include #include #define Lson rt<<1,l,m#define Rson rt<<1|1,m+1,rusing namespace std;typedef long long LL;const int maxn = 1e3+5,maxm = 2e5+5;int N;struct Edge{ int to,next;}edges[maxm];int head[maxn],tot;int linker[maxn];bool used[maxn];void init(){ tot=0; memset(head,-1,sizeof(head));}void AddEdge(int u,int v){ edges[tot].to = v; edges[tot].next = head[u]; head[u] = tot++;}bool dfs(int u){ int v,st,ed; for(int i=head[u];~i;i = edges[i].next){ v = edges[i].to; if(!used[v]){ used[v]=true; if(linker[v]==-1||dfs(linker[v])){ linker[v]=u; return true; } } } return false;}int hungary(){ int res=0; memset(linker,-1,sizeof(linker)); for(int u=1;u<=N;u++){ memset(used,0,sizeof(used)); if(dfs(u)) res++; } return res; }void Floyd(){ for(int u=1;u<=N;++u){ for(int i = head[u];~i;i =edges[i].next){ int v=edges[i].to; for(int j=head[v];~j;j=edges[j].next){ AddEdge(u,edges[j].to); } } }}void debug(){ }int main(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int T,M,u,v,tmp,k; while(scanf("%d%d",&N,&M)==2){ if(!N) break; init(); for(int i=1;i<=M;++i){ scanf("%d%d",&u,&v); AddEdge(u,v); } Floyd(); printf("%d\n",N-hungary()); } return 0;}