luogu P2764 最小路径覆盖问题

本文主要是介绍luogu P2764 最小路径覆盖问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面传送门
我们将每个点拆成入点和出点，然后每条边入点和出点连边，表示这两个点可以在一条路径上。
那么总的答案就是点数减去匹配数。
输出方案这个东西也很好搞，就是对于每个点找到答案，然后直接并查集维护即可。
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long
#define db double
#define N 300
#define M 20000
#define mod 31011
#define eps (1e-7)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
using namespace std;
int n,m,S,T,d[N+5],nows[N+5],x,y,now,fa[N+5],un,wn,ans;
struct yyy{int to,w,z;}tmp;
struct ljb{int  head,h[N+5];yyy f[M+5<<1];I void add(int x,int y,int z){f[head]=(yyy){y,z,h[x]};h[x]=head++;}}s;
I void get(int x,int y,int z){s.add(x,y,z);s.add(y,x,0);} queue<int> Q;
I int bfs(){
	while(!Q.empty()) Q.pop();yyy tmp;Me(d,0x3f);d[S]=0;Q.push(S);nows[S]=s.h[S];while(!Q.empty()){
		now=Q.front();Q.pop();for(int i=s.h[now];~i;i=tmp.z){
			tmp=s.f[i];if(!tmp.w||d[tmp.to]<1e9) continue;d[tmp.to]=d[now]+1;
			nows[tmp.to]=s.h[tmp.to];Q.push(tmp.to);if(tmp.to==T)return 1;
		}
	}return 0;
}
I int dfs(int x,int sum){
	if(x==T) return sum;yyy tmp;int i,k,pus=0;for(i=nows[x];~i;i=tmp.z){
		nows[x]=i;tmp=s.f[i];if(!tmp.w||d[tmp.to]!=d[x]+1) continue;k=dfs(tmp.to,min(sum,tmp.w));
		if(!k) d[tmp.to]=1e9;sum-=k;pus+=k;s.f[i].w-=k;s.f[i^1].w+=k;if(!sum) break;
	}return pus;
}vector<int> Ans[N+5];
I int Getfa(int x){return x==fa[x]?x:fa[x]=Getfa(fa[x]);}
I void merge(int x,int y){un=Getfa(x);wn=Getfa(y);un^wn&&(fa[un]=wn);}
int main(){
	freopen("1.in","r",stdin);
	re int i,j;Me(s.h,-1);scanf("%d%d",&n,&m);T=2*n+1;for(i=1;i<=m;i++) scanf("%d%d",&x,&y),get(x,y+n,1);for(i=1;i<=n;i++)get(S,i,1),get(i+n,T,1),fa[i]=i;
	while(bfs()) ans+=dfs(S,1e8);for(i=1;i<=n;i++) {
		for(j=s.h[i];~j;j=tmp.z)tmp=s.f[j],!tmp.w&&tmp.to&&(merge(i,tmp.to-n),0);
	}for(i=1;i<=n;i++) Ans[Getfa(i)].push_back(i);
	for(i=1;i<=n;i++) {if(!Ans[i].size()) continue;for(j=0;j<Ans[i].size();j++) printf("%d ",Ans[i][j]);printf("\n");}
	printf("%d\n",n-ans); 
}

这篇关于luogu P2764 最小路径覆盖问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！