线性规划与网络流之3 最小路径覆盖

题目：http://www.byvoid.com/blog/lpf24-solution/

分析：

求一个有向无环图的最小路径覆盖。

构造二分图，每个点拆成两个。然后按边的关系从左边向右边连边即可。

然后求最大匹配。最后输出N-最大匹配数即可。

HINT

另外也可以求无向图的最小路径覆盖。

最后答案就是N-最大匹配数/2

code:

#include #include #define E 100000
#define N 10000
int n,e,x[E],y[E],next[E],ls[N],link[N],v[N];

void add(int X,int Y,int i){
     x[i]=X; y[i]=Y; next[i]=ls[X]; ls[X]=i;
}

void init(){
     scanf("%d%d",&n,&e);
     int X,Y;
     for (int i=1;i<=e;i++){
         scanf("%d%d",&X,&Y);
         add(X,Y,i);
     }
}

bool find(int k,int mark){
     for (int t=ls[k];t!=0;t=next[t])
       if (v[y[t]]!=mark){
         int q=link[y[t]];
         link[y[t]]=k;
         v[y[t]]=mark;
         if (q==0 || find(q,mark)) return true;
         link[y[t]]=q;
     }
     return false;
}

void match(){
     memset(link,0,sizeof(link));
     memset(v,0,sizeof(v));
     int MatchNum=0;
     for (int i=1;i<=n;i++)
       if (find(i,i)) MatchNum++;
     printf("%dn",n-MatchNum);
}

int main(){
    freopen("path.in","r",stdin);
    freopen("path.ans","w",stdout);
    init();
    match();
    return 0;
}