题解 P2764 【最小路径覆盖问题】

· · 题解

讲一下思路吧，套路的拆点，将每个点拆成两个，一个入点，一个出点，

如果原图中两个点之间有一条有向边，那么就将拆点后的图该点的出点连一条容量为1的边到另一点的入点，

然后建立一个超源，超汇，把超源向每个出点连边，入点向超汇连边，然后跑最大流。

每条路径的开头就是入点中没有匹配的点，跑最大流的时候记录一下每个入点对应的出点就行了。

大家都吐槽此题没写special judge，所以用vector邻接表输出方案会不对，

所以蒟蒻为自己曾是一名pas党感到庆幸，因为pascal的邻接表写法就是大家说的链式前向星，

时空常数比较小^_^，写习惯了，就不咋用vector了。

二分图定理之一：最小路径覆盖数=顶点数-最大匹配，这个应该都知道吧？

参考代码（提交时务必手动调语言为C++，而C++11编译过不去）：

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=2000;
const int M=60010;
struct Edge{
    int to,cap,next;
}e[M*2];
int d[N],a[N],cur[N],num[N],fa[N],next[N];
bool vis[N];
queue<int> Q;
int n,m,S,T,EdgeCnt=0,tn=0;
int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
void addedge(int u,int v,int w){
    int &p=EdgeCnt;
    e[p].to=v;e[p].cap=w;e[p].next=a[u];
    a[u]=p++;
}
void BFS(){
    for (int i=1;i<=n;i++)d[i]=n;
    Q.push(T);d[T]=0;
    while (!Q.empty()){
        int u=Q.front();Q.pop();
        for (int p=a[u];p!=-1;p=e[p].next){
            int v=e[p].to;
            if (e[p^1].cap && d[v]>d[u]+1){
                d[v]=d[u]+1;
                Q.push(v);
            }
        }
    }
}
int Augment(){
    int u=T,f=INF;
    while (u!=S){
        next[fa[u]]=u;
        u=fa[u];
        f=min(f,e[cur[u]].cap);
    }
    u=T;
    while (u!=S){
        u=fa[u];
        e[cur[u]].cap-=f;
        e[cur[u]^1].cap+=f;
    }
    return f;
}
int MaxFlow(){
    n=2*n+2;
    memset(num,0,sizeof(num));
    BFS();
    for (int i=1;i<=n;i++)num[d[i]]++,cur[i]=a[i];
    int u=S,flow=0;
    while (d[S]<n){
        if (u==T){
            flow+=Augment();u=S;
        }
        bool done=false;
        for (int p=cur[u];p!=-1;p=e[p].next){
            int v=e[p].to;
            if (e[p].cap && d[u]==d[v]+1){
                done=true;fa[v]=u;cur[u]=p;u=v;
                break;
            }
        }
        if (!done){
            int m=n-1;
            for (int p=a[u];p!=-1;p=e[p].next){
                int v=e[p].to;
                if (e[p].cap)m=min(m,d[v]);
            }
            if (--num[d[u]]==0)break;
            num[d[u]=m+1]++;
            cur[u]=a[u];
            if (u!=S)u=fa[u];
        }
    }
    return flow;
}
int main(){
    memset(a,0xff,sizeof(a));
    n=read(),m=read();tn=n;
    for (int i=1;i<=m;i++){
        int u,v;
        u=read(),v=read();
        addedge(u,v+n,1);addedge(v+n,u,0);
    }
    S=2*n+1,T=2*n+2;
    for (int i=1;i<=n;i++)
        addedge(S,i,1),addedge(i,S,0),
        addedge(i+n,T,1),addedge(T,i+n,0);
    int ans=tn-MaxFlow();
    for (int i=1;i<=tn;i++)
        if (!vis[i]){
            for (int j=i;j;j=next[j]){
                if (j>tn)j-=tn;
                printf("%d ",j,next[j]);
                vis[j]=1;
            }
            printf("\n");
        }
    printf("%d",ans);
    return 0;
}