POJ2594

题目大意：

有向无环图可重叠最小路径覆盖

考虑\(u-v-w\)和\(x-v-y\)可以拆分成\(u-v-w\)和\(x-y\)，我们把所有可以到达的点之间连边，然后跑不可重叠最小路径覆盖

传递闭包用floyd

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
namespace red{
#define eps (1e-8)
    inline int read()
    {
        int x=0;char ch,f=1;
        for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
        if(ch=='-') f=0,ch=getchar();
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
        return f?x:-x;
    }
    const int N=510;
    int n,m,ret,tim;
    int f[N<<1],vis[N<<1];
    int jx[N][N];
    int head[N<<1],cnt;
    struct point
    {
        int nxt,to;
        point(){}
        point(const int &nxt,const int &to):nxt(nxt),to(to){}
    }a[N*N];
    inline void link(int x,int y)
    {
        a[++cnt]=(point){head[x],y};head[x]=cnt;
        a[++cnt]=(point){head[y],x};head[y]=cnt;
    }
    inline bool find(int x)
    {
        for(int i=head[x];i;i=a[i].nxt)
        {
            int t=a[i].to;
            if(vis[t]==tim) continue;
            vis[t]=tim;
            if(!f[t]||find(f[t]))
            {
                f[t]=x;
                return 1;
            }
        }
        return 0;
    }
    inline void main()
    {
        while("haku")
        {
            n=read(),m=read();
            if(!n&&!m) break;
            memset(head,0,sizeof(head));
            memset(jx,0,sizeof(jx));
            memset(f,0,sizeof(f));
            ret=cnt=0;
            for(int x,y,i=1;i<=m;++i)
            {
                x=read(),y=read();
                jx[x][y]=1;
            }
            for(int k=1;k<=n;++k)
            {
                for(int i=1;i<=n;++i)
                {
                    for(int j=1;j<=n;++j)
                    {
                        jx[i][j]|=jx[i][k]&jx[k][j];
                    }
                }
            }
            for(int i=1;i<=n;++i)
            {
                for(int j=1;j<=n;++j)
                {
                    if(jx[i][j]) link(i,j+n);
                }
            }
            for(int i=1;i<=n;++i)
            {
                ++tim;
                ret+=find(i);
            }
            printf("%d\n",n-ret);
        }
    }
}
signed main()
{
    red::main();
return 0;
}