最小路径覆盖

最小路径覆盖就是在一个有向图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联。对于单独的点也可以算作一条路径，长度为0.
这个问题实际上有两种细分：一种是路径不相交的，一种是路径可以相交的

不相交最小路径覆盖

将原图变为二分图，左边是入节点右边是出节点，每一条边都连一条入节点和一条出节点。然后在这个二分图上跑网络流或者匈牙利啥的都行。这样可以确保每个出节点都有只一进，保证了路径不重复。所以最小路径覆盖=原图的结点数-新图的最大匹配数。

可相交最小路径覆盖

可以相交的话需要先用floyd个跑传递闭包，之后就转化为了不相交的最小路径覆盖了。
例题：POJ2594
题意是N个点M条边的图需要多少机器人探完。
代码：

#include<cstdio>
#include<cstring>
using namespace std;
const int N=510;
int n,m,match[N],f[N][N];
bool vis[N];
bool hunguary(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]&&f[x][i])
        {
          vis[i]=1;
          if(!match[i]||hunguary(match[i])){match[i]=x;return 1;}
        }
    }
    return 0;
}
void floyed()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(f[i][k]&&f[k][j])f[i][j]=1;
}
void solve(){
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof vis);
        if(hunguary(i)) ans++;
    }
    printf("%d\n",n-ans);
}
int main(){
    while(scanf("%d%d",&n,&m)==2,n+m)
    {
        for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)f[i][j]=0;match[i]=0;}
        for(int i=1,x,y;i<=m;i++)
          scanf("%d%d",&x,&y),f[x][y]=1;
        floyed();
        solve();
    }
    return 0;
}

最小环覆盖

问题大概是这样的：给你一个N个顶点M条边的带权有向图，要你把该图分成一个或多个不相交的有向环。且所有定点都被有向环覆盖。问你该有向环所有权值的总和最小是多少?
还是建个二分图，设置每个出点到汇点的边上界为1即可，在汇点流量为n时保证每个出点都有且只有一个“前一点”。