【洛谷1345】 [USACO5.4]奶牛的电信（最小割）

传送门

Solution

emmm，直接对于每一个点拆点就好了。

然后边连Inf，点连1，跑最小割就是答案。

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=100010,Inf=1e9+10;

int front[N],cnt,s,t,n;

struct node

{

	int to,nxt,w;

}e[500010];

queue<int>Q;

int dep[N];

void Add(int u,int v,int w)

{

	e[cnt]=(node){v,front[u],w};front[u]=cnt++;

	e[cnt]=(node){u,front[v],0};front[v]=cnt++;

}

bool bfs()

{

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

	Q.push(s);dep[s]=1;

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		for(int i=front[u];i!=-1;i=e[i].nxt)

		{

			int v=e[i].to;

			if(!dep[v] && e[i].w)

			{

				dep[v]=dep[u]+1;Q.push(v);

			}

		}

	}

	return dep[t];

}

int dfs(int u,int flow)

{

	if(u==t || !flow)return flow;

	for(int i=front[u];i!=-1;i=e[i].nxt)

	{

		int v=e[i].to;

		if(dep[v]==dep[u]+1 && e[i].w)

		{

			int di=dfs(v,min(flow,e[i].w));

			if(di)

			{

				e[i].w-=di;e[i^1].w+=di;

				return di;

			}

			else dep[v]=0;

		}

	}

	return 0;

}

int dinic()

{

	int flow=0;

	while(bfs())

	{

		while(int d=dfs(s,Inf))flow+=d;

	}

	return flow;

}

int m;

int main()

{

	memset(front,-1,sizeof(front));

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

	t+=n;

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

		if(i!=s && (i!=t-n))Add(i,i+n,1);

		else Add(i,i+n,Inf);

	while(m--)

	{

		int u,v;scanf("%d%d",&u,&v);

		Add(u+n,v,Inf);

		Add(v+n,u,Inf);

	}

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

	return 0;

}

巴特西

【洛谷1345】 [USACO5.4]奶牛的电信（最小割）

传送门

Solution

代码实现

最新文章

热门文章