51nod 1321 收集点心（最小割）

给出一种最小割的方法。

设\(num1[i]\),\(num2[i]\)为第i种形状的点心的两种口味的数量

设\(type[i]\),\(type[i]\)为第i种形状的点心的两种口味

假设\(num1[i]<num2[i]\)

考虑几种最优的购买方案：

1.买\(num1[i]+1\)个点心。这样一定可以得到\(type2[i]\)。

2.买\(num2[i]+1\)个点心。这样一定可以得到\(type1[i]\)和\(type2[i]\)。

3.不买。这样连毛都得不到。

然后根据这几个购买方案建图。

把每一个点i，拆成\(i\)，\(i+n\)

设\(S\)为源点,\(T\)为汇点。

对于每一个\(i\)，\(S\)到\(i\)连容量为\(num2[i]+1\)的边，\(i+n\)到\(T\)连容量为\(num2[i]+1\)的边。

对于每一个口味，设它对应的形状为\(i\)和\(j\)，从\(i\)到\(j+n\)和\(j\)到\(i+n\)连容量为通过买形状为i或j的点心总而买到这个口味点心的最小代价的较小值。

然后跑最小割。

因为图是对称的，答案就是最小割/2

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<queue>

#include<vector>

using namespace std;

const int N=1010;

const int INF=1e9;

int n,cnt,head[N*2],ans,S,T,dis[N*2];

int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return sum*f;

}

struct node{

	int type,num;

	node(int t=0,int n=0){

		type=t,num=n;

	}

};

vector<node> vec[N];

struct edge{

	int to,nxt,flow;

}e[N*8];

void add_edge(int u,int v,int flow){

	cnt++;

	e[cnt].nxt=head[u];

	e[cnt].to=v;

	e[cnt].flow=flow;

	head[u]=cnt;

}

bool bfs(){

	queue<int> q;

	q.push(S);

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

	dis[S]=0;

	while(!q.empty()){

		int u=q.front();

		q.pop();

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

			int v=e[i].to;

			if(dis[v]==-1&&e[i].flow){

				dis[v]=dis[u]+1;

				q.push(v);

			}

		}

	}

	if(dis[T]==-1)return false;

	return true;

}

int dfs(int u,int f){

	if(u==T||f==0)return f;

	int used=0;

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

		int v=e[i].to;

		if(dis[v]==dis[u]+1&&e[i].flow){

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

			if(w){

				e[i].flow-=w;

				e[i^1].flow+=w;

				used+=w;

				if(used==f)return f;

			}

		}

	}

	if(used==0)dis[u]=-1;

	return used;

}

void Dinic(){

	while(bfs())ans+=dfs(S,INF);

}

int main(){

	n=read();

	cnt=1;

	S=0,T=n*2+1;

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

		int type1=read()+1,num1=read(),type2=read()+1,num2=read();

		if(num1>num2)swap(num1,num2),swap(type1,type2);

		vec[type1].push_back(node(i,num2+1)) ;

		vec[type2].push_back(node(i,num1+1));

		add_edge(S,i,num2+1),add_edge(i,S,0);

		add_edge(i+n,T,num2+1),add_edge(T,i+n,0);

	}

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

		int a=vec[i][0].type,b=vec[i][1].type,c=min(vec[i][0].num,vec[i][1].num);

		add_edge(a,b+n,c);add_edge(b+n,a,0);

		add_edge(b,a+n,c);add_edge(a+n,b,0);

	}

	Dinic();

	printf("%d",ans/2);

	return 0;

}

巴特西

51nod 1321 收集点心（最小割）

最新文章

热门文章