社区讨论

求助,网络流做法,本地没事,交上去T飞了

P2764最小路径覆盖问题参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo8eeka5
此快照首次捕获于
2023/10/27 17:15
2 年前
此快照最后确认于
2023/10/27 17:15
2 年前
查看原帖
rt
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=305,M=12505;
const int inf=0x3f3f3f3f;
int dist[N],flow[M],mfl=0;
int cur[N],head[N],nxt[M],to[M],tot=1,s,t;
int n,m,dep[N],f[N];
inline void add(int x,int y,int z){
	to[++tot]=y;
	nxt[tot]=head[x];
	flow[tot]=z;
	head[x]=tot;
}
inline bool bfs(){
	memset(dep,0,sizeof(dep));
	queue<int> q;
	q.push(s);dep[s]=1;
	while(q.size()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=nxt[i]){
			int u=to[i];
			if(dep[u]||!flow[i]) continue;
			dep[u]=dep[x]+1;
			q.push(u);
			if(u==t) return 1;
		}
	}
	return 0;
}
inline int dfs(int x,int now){
	if(x==t) return now;
	int res=inf;
	for(int &i=cur[x];i;i=nxt[i]){
		int u=to[i];
		if(dep[u]<=dep[x]||!flow[i]) continue;
		res=dfs(u,min(now,flow[i]));
		if(!res) dep[u]=0;
		else{
			flow[i]-=res;
			flow[i^1]+=res;
			return res;
		}
	}
}
inline int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
inline void un(int x,int y){
	x=find(x),y=find(y);
	if(x!=y) f[x]=y;
}
int main(){
	scanf("%d%d",&n,&m);
	t=n*2+1;
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y+n,1);
		add(y+n,x,0);
	} for(int i=1;i<=n;++i){
		add(s,i,1);
		add(i,s,0);
		add(i+n,t,1);
		add(t,i+n,0);
	}
	while(bfs()){
		for(int i=0;i<=t;i++) cur[i]=head[i];
		while(int now=dfs(s,inf)) mfl+=now;
	}
	mfl=n-mfl;
	for(int i=1;i<=n;++i) f[i]=i;
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=nxt[j]){
			if(!flow[j]&&to[j]-n<=n&&to[j]){
				un(i,to[j]-n);
			}
		}
	}
	vector<int> ans[155];
	for(int i=1;i<=n;i++){
		ans[find(i)].push_back(i);
	}
	for(int i=1;i<=n;i++){
		if(!ans[i].size()) continue;
		for(auto u:ans[i]){
			printf("%d ",u);
		}
		printf("\n");
	}
	printf("%d\n",mfl);
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...