【题解】SAC E#1 - 一道难题 Tree

\(\text{Solution:}\)

首先，一眼看出这是最小割，只要叶子节点对汇点\(T\)连接流量为\(inf\)的边就可以一遍最大流搞定了。

剩下的问题在于，如何判断边的方向。

可以用\(dfs\)实现，方向由源点\(S\to T.\)而边权，注意到我们连的边是双向边，且编号连续。利用这一点我们可以在\(dfs\)里面对边进行赋值。

#include<bits/stdc++.h>

using namespace std;

const int MAXN=5e5+10;

const int inf=(1<<30);

struct edge{

	int nxt,to,flow;

}e[MAXN];

int n,head[MAXN],S,T,tot=1;

int dep[MAXN],cur[MAXN],v[MAXN];

bitset<MAXN>vis;

vector<int>leaf;

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

	e[++tot].to=y;e[tot].nxt=head[x];e[tot].flow=w;head[x]=tot;

	e[++tot].to=x;e[tot].nxt=head[y];e[tot].flow=0;head[y]=tot;

}

bool bfs(int s,int t){

	memset(dep,0,sizeof(dep));

	dep[s]=1;cur[s]=head[s];

	queue<int>q;q.push(s);

	while(!q.empty()){

		s=q.front();q.pop();

		for(int i=head[s];i;i=e[i].nxt){

			int j=e[i].to;

			if(!dep[j]&&e[i].flow){

				dep[j]=dep[s]+1;

				cur[j]=head[j];

				if(j==t)return true;

				q.push(j);

			}

		}

	}

	return false;

}

int dfs(int s,int flow,int t){

	if(s==t||flow<=0)return flow;

	int rest=flow;

	for(int i=cur[s];i;i=e[i].nxt){

		int j=e[i].to;

		if(e[i].flow&&dep[j]==dep[s]+1){

			int tmp=dfs(j,min(rest,e[i].flow),t);

			if(tmp<=0)dep[j]=0;

			rest-=tmp;e[i].flow-=tmp;e[i^1].flow+=tmp;

			if(rest<=0)break;

		}

	}

	return flow-rest;

}

int dinic(int s,int t){

	int ans=0;

	while(bfs(s,t))ans+=dfs(s,inf,t);

	return ans;

}

void dfs1(int x){

	vis[x]=1;int fg=0;

	for(int i=head[x];i;i=e[i].nxt){

		int j=e[i].to;

		if(vis[j])continue;

		fg=1;dfs1(j);

		e[i].flow=v[i|1];

	}

	if(!fg)leaf.push_back(x);

}

int main(){

	scanf("%d%d",&n,&S);T=n+1;

	for(int i=1;i<n;++i){

		int a,b,c;

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,0);add(b,a,0);v[tot]=c;

	}

	dfs1(S);

	for(int i=0;i<(int)leaf.size();++i)add(leaf[i],T,inf);

	printf("%d\n",dinic(S,T));

	return 0;

}

巴特西

【题解】SAC E#1 - 一道难题 Tree

最新文章

热门文章