洛谷 P2764 最小路径覆盖问题

题面

题目传送

给定有向图 $G=(V,E)$ 。设 $P$ 是 $G$ 的一个简单路(顶点不相交)的集合。如果 $V$ 中每个定点恰好在$P$的一条路上,则称 $P$ 是 $G$ 的一个路径覆盖。$P$中路径可以从 $V$ 的任何一个定点开始,长度也是任意的,特别地,可以为 $0$ 。$G$ 的最小路径覆盖是 $G$ 所含路径条数最少的路径覆盖。设计一个有效算法求一个 GAP (有向无环图) $G$ 的最小路径覆盖。
提示:设 $V=\{1,2,…,n\}$ ,构造网络 $G_1=\{V_1,E_1\}$ 如下: $$V_1=\{x_0,x_1,…,x_n\}\cup\{y_0,y_1,…,y_n\}$$ $$E_1=\{(x_0,x_i):i\in V\}\cup\{(y_i,y_0):i\in V\}\cup\{(x_i,y_j):(i,j)\in E\}$$ 每条边的容量均为 $1$ ,求网络 $G_1$ 的 $(x_0,y_0)$ 最大流。
一句话题面:给出一张图,用 $k$ 条链去覆盖它,求出最少的链数和覆盖方案。

输入输出格式

输入格式

第一行有 $2$ 个正整数 $n$ 和 $m$ 。 $n$ 是给定$\text{GAP}$(有向无环图) $G$ 的顶点数, $m$ 是 $G$ 的边数。接下来的 $m$ 行,每行有两个正整数 $i$ 和 $j$ 表示一条有向边 $(i,j)$。

输出格式

从第 1 行开始,每行输出一条路径。文件的最后一行是最少路径数。

思路

对于一个点 $i$,将其拆成 $x_i,y_i$ 两个点。所有 $x_i$ 连接源点 $S$,所有 $y_i$ 连接汇点 $T$。

对于一条边 $(u,v)$,连边 $x_u,x_v$。

现在这张图变成了一张二分图,二分图中,最小路径覆盖 = 点的总数 – 网络最大流

最后从 $S$ 到 $T$ 跑一遍最大流。

证明

选出 $k$ 条链,也就是选出 $k$ 个集合,每个集合中的点的度数最多为 $2$。

对于一个点 $i$,当边 $(S,x_i)$ 和 $(y_i,T)$ 都被用掉时,这个点就不可能再被选,这就保证了每个点度数最多为 $2$。增广路只会经过两个节点,在同一集合中。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,last[200005],to[200005],nextt[200005],s[200005],top=1;
long long v[200005],d[200005],from[200005];
long long fa[200005];
void reset(){
	for (int i=1;i<=200000;i++){
		fa[i]=i;
	}
}
int getfa(int x){
	return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
void merge(int x,int y){
	fa[getfa(y)]=getfa(x);
}
void add(int a,int b,int c){
    nextt[++top]=last[a];
    from[top]=a;
    to[top]=b;
    s[top]=c;
    last[a]=top;
}
bool bfs(long long S,long long T){
    memset(v,0,sizeof(v));
    memset(d,63,sizeof(d));
    queue<long long> q;
    q.push(S);
    v[S]=1;
    d[S]=0;
    while (!q.empty()){
        long long now=q.front();
        q.pop();
        v[now]=0;
        for (int i=last[now];i;i=nextt[i]){
            int j=to[i];
            if (d[j]>d[now]&&s[i]){
            	d[j]=d[now]+1;
            	if (!v[j]){
	            	q.push(j);
	            	v[j]=1;
				}
			}
        }
    }
    if (d[T]<1000000000){
    	return 1;
	}
    return 0;
}
int dfs(long long x,long long minn,long long T){
	if (x==T){
		return minn;
	}
	int tmp=0;
	for (int i=last[x];i;i=nextt[i]){
        int j=to[i];
        if (d[j]==d[x]+1&&s[i]){
			tmp=dfs(j,min(minn,s[i]),T);
			if (tmp){
	            s[i]-=tmp;
	            s[i^1]+=tmp;
	            return tmp;
			}
		}
    }
    return 0;
}
long long dinic(long long S,long long T){
	long long ans=0,tmp=0;
	while (bfs(S,T)){
		while (1){
			tmp=dfs(S,2147483647,T);
			if (!tmp){
				break;
			}
			ans+=tmp;
		}
	}
	reset();
	for (int i=1;i<=top;i++){
		if (s[i]==0&&from[i]>=1&&from[i]<=n&&to[i]>=n+1&&to[i]<=n*2){
			merge(from[i],to[i]-n);
		}
	}
    return ans;
}
int main(){
	reset();
    long long S=301,T=302;
    cin>>n>>m;
    for (int i=1;i<=n;i++){
    	add(S,i,1);
    	add(i,S,0);
    	add(n+i,T,1);
    	add(T,n+i,0);
	}
    for (int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        add(a,n+b,1);
        add(n+b,a,0);
    }
    bfs(S,T);
    dinic(S,T);
    int cnt=0;
    for (int i=1;i<=n;i++){
    	bool e=0;
    	for (int j=1;j<=n;j++){
    		if (getfa(j)==i){
    			cout<<j<<" ";
    			e=1;
			}
		}
		if (e){
			cnt++;
			cout<<endl;
		}
	}
	cout<<cnt<<endl;
}

 

暂无评论

发送评论 编辑评论


				
上一篇
下一篇