济南网站建设培训学校/长沙做引流推广的公司

分析：我们仍可将问题转化为最小路径覆盖。如果一个人需要经过另一个人走过的点的时候，让他直接从该点上空飞过去，越过该点，直接走下一个点。如果我们赋予每个人这种能力，那么求得的无重复点的最小路径覆盖结果，就是题目要求的结果，因为需要重复的地方只要飞过去，就可以不重复了。赋予这个能力的方法就是把所有点能间接到达的点全都改为直接到达。然后正常求最小路径覆盖即可。

做法就是先求出可达矩阵，在其上求最小路径覆盖（n-最大匹配）。可达矩阵可以用floyd来求，复杂度n的三次方没跑了。

当然，也可以在每个点上做一遍dfs，这只需要nm的复杂度，依题意m小于n方，所以这种改进是有意义的。可以进一步，对每个点的所有后继做dfs，然后将当前点连上所有后继可达的点（此处需要一个数组来标记是否已经添加过了）。这样改进之后时间耗时大大的缩短了。

floyd版本的。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define N 505
int n,m,g[N][N];
int used[N],link[N];
int dfs(int i){for(int j = 1;j<=n;j++)if(g[i][j] && !used[j]){used[j] = 1;if(link[j]==-1 || dfs(link[j])){link[j] = i;return 1;}}return 0;
}
int hungary(){int res = 0;for(int i = 1;i<=n;i++){memset(used,0 , sizeof(used));if(dfs(i))res++;}return res;
}
int main(){while(scanf("%d %d",&n,&m) && (n+m)){int i,j,k;memset(g, 0, sizeof(g));memset(link, -1, sizeof(link));for(i = 0;i<m;i++){int a,b;scanf("%d %d",&a,&b);g[a][b] = 1;}for(k = 1;k<=n;k++)for(i = 1;i<=n;i++)for(j = 1;j<=n;j++)if(g[i][k] && g[k][j])g[i][j] = 1;printf("%d\n",n-hungary());}return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define N 505
int n,m;
int used[N],link[N];
struct edge{int y,next;
}tmp[5005],e[N*N/2];
int ftmp[N],first[N],hh[N][N];
int ttmp,top;
void atmp(int x,int y){tmp[ttmp].y = y;tmp[ttmp].next = ftmp[x];ftmp[x] = ttmp++;
}
void add(int x,int y){e[top].y = y;e[top].next = first[x];first[x] = top++;
}
void graph(int x){used[x] = 1;for(int i = ftmp[x];i!=-1;i=tmp[i].next){if(!used[tmp[i].y])graph(tmp[i].y);hh[x][tmp[i].y] = 1;add(x,tmp[i].y);for(int j = first[tmp[i].y];j!=-1;j=e[j].next)if(!hh[x][e[j].y]){add(x,e[j].y);hh[x][e[j].y] = 1;}}
}
int dfs(int x){for(int i = first[x];i!=-1;i=e[i].next){if(!used[e[i].y]){used[e[i].y] = 1;if(link[e[i].y]==-1 || dfs(link[e[i].y])){link[e[i].y] = x;return 1;}}}return 0;
}
int hungary(){int res = 0;for(int i = 0;i<=n;i++){memset(used, 0, sizeof(used));if(dfs(i))res++;}return res;
}
int main(){while(scanf("%d %d",&n,&m) && (n+m)){memset(ftmp, -1, (1+n)*sizeof(ftmp));memset(first,-1,(1+n)*sizeof(first));memset(used, 0, (1+n)*sizeof(used));memset(link, -1, (1+n)*sizeof(link));for(int i = 1;i<=n;i++)for(int j = 1;j<=n;j++)hh[i][j] = 0;ttmp = top = 0;for(int i = 0;i<m;i++){int a,b;scanf("%d %d",&a,&b);atmp(a,b);}for(int i = 1;i<=n;i++)if(!used[i])graph(i);printf("%d\n",n-hungary());}return 0;
}