题目：http://poj.org/problem?id=2594
最小路径覆盖， 要求每个点只经过一次。
此题说明一个点可以经过无数次。。那么.....
刚开始看到。。。狂wa
当数据为
5 4
1 2
2 3
4 2
2 5
时，求匹配时在用到4之前，2已经被匹配了，4这里就找不到匹配的了，4和5也就成孤立点了
用最最小路径求的1-》2-》3后，2就被删除了，4和5就连不起来了，所以
用floyd求某两点之间是否可达..然后用新图求最小路径覆盖.....
代码：
View Code
1 #include<stdio.h>
2 #include<string.h>
3 #define maxn 501
4 int mark[maxn];
5 bool map[maxn][maxn],visit[maxn];
6 int n,m;
7 bool dfs(int k)
8 {
9 int i;
10 for(i=1;i<=n;i++)
11 {
12 if(map[k][i]&&!visit[i])
13 {
14 visit[i]=1;
15 if(mark[i]==-1||dfs(mark[i]))
16 {
17 mark[i]=k;
18 return 1;
19 }
20 }
21 }
22 return 0;
23 }
24
25 int solve()
26 {
27 int i,num=0;
28 for(i=1;i<=n;i++)
29 {
30 memset(visit,0,sizeof(visit));
31 if(dfs(i))
32 num++;
33 }
34 return n-num;
35 }
36
37 void init()
38 {
39 memset(map,0,sizeof(map));
40 memset(mark,-1,sizeof(mark));
41 }
42
43 //使图上的路径没有交叉
44 void floyd()
45 {
46 int i,j,k;
47 for(k=1;k<=n;k++)
48 for(i=1;i<=n;i++)
49 for(j=1;j<=n;j++)
50 if(map[i][k]&&map[k][j])
51 map[i][j]=1;
52 }
53
54 int main()
55 {
56 int x,y;
57 while(scanf("%d%d",&n,&m)!=EOF&&n+m!=0)
58 {
59 init();
60 while(m--)
61 {
62 scanf("%d%d",&x,&y);
63 map[x][y]=1;
64 }
65 floyd();
66 printf("%d\n",solve());
67 }
68 return 0;
69 }