[BZOJ1934][SHOI2007]Vote 善意的投票：最小割

分析

先讲一下连边方法：

\(S\)向意愿同意的人，意愿反对的人向\(T\)，朋友之间互相连（其实好像意愿不同的朋友之间互相连就可以了，嘛，不管了），容量均为\(1\)。

最小割即为答案。

可以理解为，一个人要么背叛自己的意愿，要么背叛自己的友情，背叛可以理解为割掉对应的边。（QwQ）

在做这种“每个对象有两种或更多种决策，且一个对象的决策会影响到其他对象，想要达到全局最优”类似的题目时，可以考虑一下转化为最小割模型，不要执着于DP和贪心。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

#include <queue>

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

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

#define trav(i,a) for(int i=head[(a)];i;i=e[i].nxt)

using std::cin;

using std::cout;

using std::endl;

typedef long long LL;

inline int read(){

	int x=0;char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x;

}

const int MAXN=305;

const int MAXM=45605;

int n,m,S,T,maxflow,mincut;

int ecnt=1,head[MAXN];

int dep[MAXN],cur[MAXN];

std::queue<int> q;

struct Edge{

	int to,nxt,cap;

}e[MAXM<<1];

inline void add_edge(int bg,int ed,int ca){

	ecnt++;

	e[ecnt].to=ed;

	e[ecnt].nxt=head[bg];

	e[ecnt].cap=ca;

	head[bg]=ecnt;

}

inline bool bfs(){

	memset(dep,0,sizeof dep);

	rin(i,1,T) cur[i]=head[i];

	while(!q.empty()) q.pop();

	q.push(S);

	dep[S]=1;

	while(!q.empty()){

		int x=q.front();

		q.pop();

		trav(i,x){

			int ver=e[i].to;

			if(dep[ver]||!e[i].cap) continue;

			dep[ver]=dep[x]+1;

			q.push(ver);

		}

	}

	return dep[T]>0;

}

int dfs(int x,int pref){

	if(x==T||!pref) return pref;

	int flow=0,temp;

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

		int ver=e[i].to;

		if(dep[ver]==dep[x]+1&&(temp=dfs(ver,std::min(e[i].cap,pref)))){

			e[i].cap-=temp;

			e[i^1].cap+=temp;

			flow+=temp;

			pref-=temp;

			if(!pref) return flow;

		}

	}

	return flow;

} 

inline void dinic(){

	while(bfs()) maxflow+=dfs(S,1e9);

}

int main(){

	n=read(),m=read();

	S=n+1,T=S+1;

	rin(i,1,n){

		int typ=read();

		if(typ) add_edge(S,i,1),add_edge(i,S,0);

		else add_edge(i,T,1),add_edge(T,i,0);

	}

	rin(i,1,m){

		int u=read(),v=read();

		add_edge(u,v,1);

		add_edge(v,u,1);

	}

	dinic();

	mincut=maxflow;

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

	return 0;

}

巴特西

[BZOJ1934][SHOI2007]Vote 善意的投票：最小割

分析

代码

最新文章

热门文章