Codeforces 343E 最小割树

概述题意及思路：https://www.cnblogs.com/Yuzao/p/8494024.html 最小割树的实现参考了这篇博客：https://www.cnblogs.com/coder-Uranus/p/9771919.html 代码： #include <bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;const

题意及思路：https://www.cnblogs.com/Yuzao/p/8494024.html

最小割树的实现参考了这篇博客：https://www.cnblogs.com/coder-Uranus/p/9771919.html

代码：

#include <bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;const int maxn = 210;const int maxm = 2010;int head[maxn],Next[maxm],ver[maxm],edge[maxm],d[maxn];int n,m,s,t,tot,maxflow;int head1[maxn],Next1[maxm],ver1[maxm],edge1[maxm],tot1;bool v1[maxm];int ans = 0;int mi,mi_ID;int a[maxn],b[maxn];queue<int> q;struct Edge {	int u,v,w;};Edge e[maxm];voID add(int x,int y,int z) {	ver[++tot] = y,edge[tot] = z,Next[tot] = head[x],head[x] = tot;	ver[++tot] = x,Next[tot] = head[y],head[y] = tot;}voID add1(int x,int z) {	ver1[++tot1] = y,edge1[tot1] = z,Next1[tot1] = head1[x],head1[x] = tot1;	ver1[++tot1] = x,Next1[tot1] = head1[y],head1[y] = tot1;}voID init() {	memset(head,sizeof(head));	tot = 1;	for (int i = 1; i <= m; i++)		add(e[i].u,e[i].v,e[i].w);}bool bfs() {	memset(d,sizeof(d));	while(q.size()) q.pop();	q.push(s); d[s] = 1;	while(q.size()) {		int x = q.front(); q.pop();		for (int i = head[x]; i; i = Next[i]) {			if(edge[i] && !d[ver[i]]) {				q.push(ver[i]);				d[ver[i]] = d[x] + 1;				if(ver[i] == t) return 1;			}		}	}	return 0;}int dfs(int x,int flow) {	if(x == t) return flow;	int rest = flow,k;	for (int i = head[x]; i && rest; i = Next[i]) {		if(edge[i] && d[ver[i]] == d[x] + 1) {			k = dfs(ver[i],min(rest,edge[i]));			if(!k) d[ver[i]] = 0;			edge[i] -= k;			edge[i ^ 1] += k;			rest -= k;		}	}	return flow - rest;}voID dinic(int x,int y) {	s = x,t = y;	init();	int flow = 0;	maxflow = 0;	while(bfs())		while(flow = dfs(s,INF)) maxflow += flow;}voID build(int l,int r) {	if(l == r) return;	int x = a[l],y = a[l + 1];	dinic(x,y);	int L = l - 1,R = r + 1;	for (int i = l; i <= r; i++) {		if(d[a[i]] == 0) b[--R] = a[i];		else b[++L] = a[i]; 	}	for (int i = l; i <= r; i++)		a[i] = b[i];	add1(x,y,maxflow);	//cout << maxflow << endl;	ans += maxflow;	build(l,L);	build(R,r);}voID dfs1(int x,int fa) {	for (int i = head1[x]; i; i = Next1[i]) {		int y = ver1[i],z = edge1[i];		if(v1[i]) continue;		if(y == fa) continue;		if(z < mi) {			mi = z;			mi_ID = i;		}		dfs1(y,x);	}}voID print(int x) {	mi = INF,mi_ID = -1;	dfs1(x,-1);	int Mi_ID = mi_ID;	if(Mi_ID == -1) {		printf("%d ",x);		return;	}	v1[Mi_ID] = v1[Mi_ID ^ 1] = 1;	print(ver1[Mi_ID]);	print(ver1[Mi_ID ^ 1]);}int main() {	tot1 = 1;	scanf("%d%d",&n,&m);	for (int i = 1; i <= m; i++) {		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);	}	for (int i = 1; i <= n; i++) a[i] = i;		build(1,n);	printf("%d\n",ans);	print(1);} 

总结

以上是内存溢出为你收集整理的Codeforces 343E 最小割树全部内容，希望文章能够帮你解决Codeforces 343E 最小割树所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。