[题解] LuoguP2764 最小路径覆盖问题

好久没做网络流方面的题发现自己啥都不会了qwq

题意：给一张有向图，让你用最少的简单路径覆盖所有的点。

考虑这样一个东西，刚开始，我们有\(n\)条路径，每条路径就是单一的一个点，那么我们的目的就是进行若干次操作将路径两两合并，这样对于一个以节点\(x\)，它作为路径的端点最多被合并两次（一次连出边一次连入边）。

于是考虑二分图，将点\(x\)炸成两个点\(x_0,x_1\)，\(x_0\)表示\(x\)连出去的出边，\(x_1\)表示\(x\)连进来的入边。那么对于图上一条\(u \rightarrow v\)的路径，在\(u_0,v_1\)之间连一条边，表示合并一条\(u\)为端点的路径和一条\(v\)为端点的路径。

这样，在合法的情况下最大的合并次数就是这张二分图的最大匹配数。

最小的路径条数就是\(n-\)最大匹配。匈牙利或者网络流啥的求出最大匹配，然后打印方案的话就对整张图照着最大匹配中的边\(Dfs\)一遍。

网络流的代码还是感觉匈牙利好写......：

#include <bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for (int i=(a);i<(b);++i)

#define per(i,a,b) for (int i=(a)-1;i>=(b);--i)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define all(x) (x).begin(),(x).end()

#define SZ(x) ((int)(x).size())

typedef double db;

typedef long long ll;

typedef pair<int,int> PII;

typedef vector<int> VI;

const int N=1e5+10,INF=0x3f3f3f3f;

struct Dinic {

	int n,S,T;

	int to[N<<1],nxt[N<<1],fst[N],cap[N<<1],flow[N<<1],cnt=0;

	inline void ade(int x,int y,int w) {

		to[++cnt]=y,cap[cnt]=w,flow[cnt]=0;

		nxt[cnt]=fst[x],fst[x]=cnt;

	}

	inline void addedge(int x,int y,int w) {ade(x,y,w),ade(y,x,0);}

	int d[N],q[N];

	bool bfs() {

		rep(i,0,n+1) d[i]=0;

		int tn=1; q[0]=S;

		d[S]=1;

		rep(_,0,tn) {

			int u=q[_];

			for(int i=fst[u];i;i=nxt[i]) {

				int v=to[i];

				if(d[v]==0&&cap[i]>flow[i]) {

					d[v]=d[u]+1;

					q[tn++]=v;

				}

			}

		}

		return d[T]!=0;

	}

	int cur[N];

	int dfs(int x,int ag) {

		if(x==T||ag==0) return ag;

		for(int &i=cur[x];i;i=nxt[i]) {

			int v=to[i];

			if(cap[i]>flow[i]&&d[v]==d[x]+1) {

				int out=dfs(v,min(ag,cap[i]-flow[i]));

				if(out) {

					flow[i]+=out;

					flow[i^1]-=out;

					return out;

				}

				else d[v]=0;

			}

		}

		return 0;

	}

	int Maxflow() {

		int ans=0,out=0;

		while(bfs()) {

			rep(i,0,n+1) cur[i]=fst[i];

			while(out=dfs(S,1e9)) ans+=out;

		}

		return ans;

	}

	void init(int tn,int s,int t) {

		S=s,T=t,n=tn;

		rep(i,0,n+1) fst[i]=0;

		cnt=1;

	}

}flow;

#define IDL(x) (x)

#define IDR(x) ((x)+n)

#define NODE(x) ((x)<=n?(x):(x)-n)

int n,m;

int vis[233][233],mark[N];

VI g[N];

void dfs(int x) {

	printf("%d ",x);

	mark[x]=1;

	for(auto v:g[x]) if(vis[x][v])

		dfs(v);

}

int main() {

	scanf("%d%d",&n,&m);

	const int S=n*2+1,T=n*2+2;

	flow.init(n*2+5,S,T);

	rep(i,1,n+1) flow.addedge(S,IDL(i),1),flow.addedge(IDR(i),T,1);

	rep(i,0,m) {

		int x,y; scanf("%d%d",&x,&y);

		flow.addedge(IDL(x),IDR(y),INF);

		g[x].pb(y);

	}

	int ans=n-flow.Maxflow();

	rep(i,2,flow.cnt+1) if(flow.flow[i]==1)

		vis[NODE(flow.to[i^1])][NODE(flow.to[i])]=1;

	rep(i,1,n) if(!mark[i]) dfs(i),puts("");

	printf("%d\n",ans);

	return 0;

}

巴特西

[题解] LuoguP2764 最小路径覆盖问题

最新文章

热门文章