最小边覆盖（最小路径覆盖）（路径可相交）——pku2594

一开始没看到You should notice that the roads of two different robots may contain some same point. WA了好几次

它是说如果

1-2

2-3

那么1-3

图的传递性可以用floyd快速求解

#include<stdio.h>
#include<math.h>
#include<string.h>

int g,m;

bool map[509][509];
int mark[509];
bool flag[509];

bool dfs(int x)
{
    int i;
    for(i=1;i<=m;i++)
    {
        if(map[x][i]==0||flag[i]) continue;
        flag[i]=1;
        if(mark[i]==0||dfs(mark[i]))
        {
            mark[i]=x;
            return 1;
        }
    }
    return 0;
}

int main()
{
    int n,p;
    while(scanf("%d%d",&p,&n),n||p)
    {
        memset(mark,0,sizeof(mark));
        memset(map,0,sizeof(map));

        g=m=p;
        
        
        int i;
        for(i=1;i<=n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            map[a][b]=1;
        }
        
        int k,j;
        for(k=1;k<=p;k++)
            for(i=1;i<=p;i++)
                for(j=1;j<=p;j++)
                {
                    if(!map[i][j]&&map[i][k]&&map[k][j])
                        map[i][j]=1;
                }

        int count=0;
        for(i=1;i<=g;i++)
        {
            memset(flag,0,sizeof(flag));
            if(dfs(i)) count++;
        }

        printf("%d\n",p-count);
    }
}