最小路径覆盖问题解题报告

S1

听到昊哥和ZYC(~~尽管我已经不信他了~~)在讨论这道题……萌生了做一做的冲动。
先考虑建图。对于每条路径来说，都有一个自己的源点与汇点，所以每个点都应该连接源点与汇点，优先考虑拆点，拆完一个连源点，一个连汇点。跟两个巨佬交流了一下，好像就是这么建图……
这时我突然想到一个GG的事情，如果每个点都连源点和汇点，最大流跑出来岂不是所有点的总和？问了几个巨佬都说不是啊这使我这蒟蒻一脸懵逼只能去看题解。

S2

题解里的建图和我的只差一点，那就是把一个点拆成两个，一个出点专门往外出发出边，一个入点专门接受边，源点向出点引一条边，入点向汇点引一条边。
之前有个叫ZYC(~~没错又是你小子给我等着~~)的人告诉我路径长度可以为0，又把我给误导了……这个题的意思是最小路径覆盖，所以虽然路径长度可以为0，但是网络流是跑不出来的，也就是说在跑网络流的时候不能把单点看做一条路径，这个怎么处理后面说。
我们先论证一下这种建图方式的正确性。首先我们知道，每两个点被覆盖，就多一条路径被覆盖，所以我们每次增广，只增广两个点一条边就够了，也就是说，按照之前的建图方案，源点向a点出点有一个流量，a点出点向b点入点传递，b点入点流到汇点。
那么这样跑出来的是什么？是最大匹配数，也就是被覆盖的路径数。当然，我说的被覆盖的路径数是相对于单个路径，而不是题目中所说的路径。
这里有两种理解方法，一种是数学上的。我们把这个图看做几个路径构成的集合，那么去掉那些多余的边，那么边数就相当于顶点数-1，我们把每个路径看做一个大点，那么连接每个路径的边数就相当于路径数-1，我们可以推出公式： (answer为最终结果，ans为网络流跑出来的结果，point为总点数,road为连接每个大点(即路径)的边数)

    Num(road)=(Num(point)-1)-ans;
    
    Num(road)=answer-1;
    
    answer=Num(point)-ans;

这也证明了第二种方法，即二分图的一个原理。我们知道这个图是每个出点连接源点，每个入点连接汇点，两两对称，所以可以用二分图的性质来做。二分图的一个重要性质为最小路径覆盖数=总点数-最大匹配数，证明如上。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define inb inline bool
#define ini inline int
#define big 1e9
using namespace std;
int n,m,k,cnt,head[100000],cur[100000],dis[100000],ans,tot,s=0,t=1001,a[1001],b[1001];
struct node
{
    int from,to,dis,num,next;
}ljb[250000];
ini read()
{
    char c;int r=0;
    while (c<'0' || c>'9') c=getchar();
    while (c>='0' && c<='9')
    {
        r=r*10+c-'0';
        c=getchar();
    }
    return r;
}
inv add_edge(int x,int y,int z)
{
    ljb[++cnt].from=x;
    ljb[cnt].to=y;
    ljb[cnt].dis=z;
    ljb[cnt].num=cnt;
    ljb[cnt].next=head[x];
    head[x]=cnt;
}
inv add(int x,int y,int z)
{
	add_edge(x,y,z);
	add_edge(y,x,0);
}
queue<int> q;
inb bfs()
{
    q.push(s);
    memset(dis,128,sizeof(dis));
    dis[s]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for (rint i=head[x];i!=-1;i=ljb[i].next)
        {
            int y=ljb[i].to;
            if (dis[y]<0 && ljb[i].dis>0)
            {
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    if (dis[t]>0) return 1;
    return 0;
}
ini dfs(int x,int low)
{
    if (x==t) return low;
    for (rint& i=cur[x];i!=-1;i=ljb[i].next)
    {
        int y=ljb[i].to;
        if (dis[y]==dis[x]+1 && ljb[i].dis>0)
        {
            int flow=dfs(y,min(low,ljb[i].dis));
            if (flow)
            {
                ljb[i].dis-=flow;
                ljb[ljb[i].num^1].dis+=flow;
                return flow;
            }
        }
    } 
    return 0;
} 
int main()
{
	n=read();m=read();
	for (rint i=s;i<=t;i++) head[i]=-1;cnt=-1;
	for (rint i=1;i<=m;i++)
	{
		int x,y;x=read();y=read();
		add(x,y+n,1);
	}
	for (rint i=1;i<=n;i++)
	{
		add(s,i,1);
		add(i+n,t,1);
	}
	while (bfs())
	{
		for (rint i=s;i<=t;i++) cur[i]=head[i];
		do
		{
			tot=dfs(s,big);
			ans+=tot;	
		} 
		while (tot);
	}
	for (rint i=0;i<=cnt;i+=2)
		if (ljb[i].dis==0 && ljb[i].from!=s && ljb[i].to!=t) 
		{
			a[ljb[i].from]=ljb[i].to-n;
			b[ljb[i].to-n]=ljb[i].from;
		}
	for (rint i=1;i<=n;i++)
	{
		if (!b[i])
		{
			int x=i;
			while (x)
			{
				cout<<x<<" ";
				x=a[x];
			}
			cout<<endl;
		} 
	}
	printf("%d",n-ans);
}

总结

不要怕磨时间，也不要怕看题解，吃透题的每一个细节。
在提交代码之前尽量少和别人交流，除非走投无路，万一被误导就不好了。
拆点之后的两个点不一定都连接，不要被套路所束缚。
答案不一定必须是最大流跑出来的结果，积极尝试答案是总集合减去最大流该怎么建图。

最是套路得人心

S1

S2

代码

总结