最小路径覆盖

路径覆盖

路径覆盖指一个路径的集合中所有路径点集的并集为原图点集。最小路径覆盖使路径集合大小最小。

路径覆盖分为可否重复选点两种。可重复选点在建模中加大流量即可。

网络流模型

建超级源 \(S\) 和超级汇 \(T\)，将每个点拆点。
将 \(S\) 向所有点 \(i\) 连边，将所有点 \(i'\) 向 \(T\) 连边。
对于原图边集，每一条边 \(u\) 向 \(v'\) 连边。
选点不重的最小路径覆盖问题，上述所有边流量为 1，答案为点数减去最小割。

考虑对于这个模型建出来的图求出的最小割是什么。它实际上是最大的可以合并的路径条数。因为每合并两条路径相当于总路径数就减少了，所以有最小路径覆盖等于点数减最大匹配。

其中最大匹配就是我们刚才的模型。可以发现，我们实际上就是建了一个二分图在求最大匹配。

P2764 最小路径覆盖问题

题意如上，要求构造方案。

我的构造方式如下：利用并查集，对于每条道路的端点，若这条边被选择了就将这两条边加入一个并查集，每个并查集代表一条路径。最后从每个路径的起点进行一遍搜索即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=305,maxm=6305,S=303,T=304,INF=0x3f3f3f3f;
	int n,m;
	int ecnt=1,head[maxn],cur[maxn],to[maxm<<1],nxt[maxm<<1],w[maxm<<1];
	inline void addedge(int a,int b,int c){
		to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt,w[ecnt]=c;
		to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt,w[ecnt]=0;
	}
	int dep[maxn];
	inline bool bfs(){
		memset(dep,-1,sizeof dep);
		static int q[maxn];
		int hd=0,tl=1;
		q[tl]=S;dep[S]=0;
		while(hd<tl){
			int x=q[++hd];
			for(int u,i=head[x];i;i=nxt[i]) if(dep[u=to[i]]==-1 and w[i])
				dep[u]=dep[x]+1,q[++tl]=u;
		}
		return dep[T]!=-1;
	}
	int dfs(int x,int flow){
		if(x==T) return flow;
		int used=0,u;
		for(int& i=cur[x];i;i=nxt[i]) if(dep[u=to[i]]==dep[x]+1 and w[i]){
			int v=dfs(u,min(flow-used,w[i]));
			used+=v,w[i]-=v,w[i^1]+=v;
			if(used==flow)break;
		}
		return used;
	}
	inline int dinic(){
		int ans=0;
		while(bfs()) memcpy(cur,head,sizeof head),ans+=dfs(S,INF);
		return ans;
	}
	int fa[maxn];
	bool vis[maxn];
	int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	void Dfs(int x){printf("%d ",x);for(int u,i=head[x];i;i=nxt[i]) if(!w[i] and (u=to[i])>n and u<=n*2) Dfs(u-n);}
	inline void work(){
		n=read(),m=read();
		for(int u,v,i=1;i<=m;i++) u=read(),v=read(),addedge(u,v+n,1);
		for(int i=1;i<=n;i++) addedge(S,i,1),addedge(i+n,T,1),fa[i]=i;
		int ans=n-dinic();
		for(int i=1;i<=m;i++) if(!w[i<<1]) fa[find(to[i<<1]-n)]=find(to[i<<1|1]);
		for(int i=1;i<=n;i++) if(find(i)==i) Dfs(i),puts("");
		printf("%d\n",ans);
	}
}
signed main(){
	star::work();
	return 0;
}

P2469 星际竞速

题意

给你若干单向道路，并且每个点有一个可以从任意位置任意时刻到达该点的代价。求遍历所有点的最小代价。

思路

参照最小路径覆盖的思路，拆出来的第二个点与汇点间的连边表示到达该点。建模方式如下：

对于所给的所有边 \((u,v)\)，将 \(u\) 向 \(v'\) 建边权费用边。
从源点向所有 \(i\) 连无费用边。
从所有 \(i'\) 向汇点连无费用边。
从源点向所有 \(i'\) 连传送费用边。上述所有边流量为 1。（因为从任何位置传送与起点无关）

跑最小费用最大流即为答案。正确性，考虑建出来的图，因为源点到所有点都有传送的边，所以跑最小割一定会经过所有点，并且因为都是单向边且流量为 1，所以保证正确。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=3005,maxm=600005,S=3003,T=3004,INF=0x3f3f3f3f;
	int n,m;
	int ecnt=1,head[maxn],to[maxm],nxt[maxm],w[maxm],v[maxm];
	inline void addedge(int a,int b,int c,int d){
		to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt,w[ecnt]=c,v[ecnt]=d;
		to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt,w[ecnt]=0,v[ecnt]=-d;
	}
	int dis[maxn],pre[maxn];
	bool vis[maxn];
	inline bool spfa(){
		queue<int> q;
		memset(pre,0,sizeof pre);
		memset(vis,0,sizeof vis);
		memset(dis,INF,sizeof dis);
		q.push(S);dis[S]=0;
		while(!q.empty()){
			int x=q.front();q.pop();
			vis[x]=false;
			for(int u,i=head[x];i;i=nxt[i]) if(dis[u=to[i]]>dis[x]+v[i] and w[i]){
				dis[u]=dis[x]+v[i];pre[u]=i;
				if(!vis[u]) vis[u]=true,q.push(u);
			}
		}
		return pre[T];
	}
	int a[maxn];
	inline void work(){
		n=read(),m=read();
		for(int i=1;i<=n;i++) addedge(S,i,1,0),addedge(i+n,T,1,0),addedge(S,i+n,1,a[i]=read());
		for(int u,v,zp,i=1;i<=m;i++){
			u=read(),v=read();
			if(u>v) swap(u,v);
			if((zp=read())<a[v])addedge(u,v+n,1,zp);
		}
		int ans=0;
		while(spfa()){
			int mn=INF;
			for(int i=pre[T];i;i=pre[to[i^1]]) mn=min(mn,w[i]);
			for(int i=pre[T];i;i=pre[to[i^1]]) w[i]-=mn,w[i^1]+=mn;
			ans+=dis[T]*mn;
		}
		printf("%d\n",ans);
	}
}
signed main(){
	star::work();
	return 0;
}