【CF331E】Biologist（网络流，最小割）

时间：2023-03-09 18:51:20
【CF331E】Biologist（网络流，最小割）

【CF311E】Biologist（网络流，最小割）

题面

洛谷

翻译：

有一个长度为\(n\)的\(01\)串，将第\(i\)个位置变为另外一个数字的代价是\(v_i\)。

有\(m\)个要求

每个要求的形式是

首先确定若干位置都要是\(0\)或者\(1\)

然后给定这\(K\)个位置，如果些位置上都满足要求

那么就可以得到\(W_k\)元

某些要求如果失败了还要倒着给\(g\)元

问最终能够得到的最大利润

输入格式：

第一行是\(n,m,g\)

第二行是\(V_i\)

接下来\(m\)行

第一个数字表示这个集合都要是\(0\)还是\(1\)

第二个数字\(W_i\)表示利润，接下来\(k_i\)表示这个集合中有\(k\)个位置

接下来是这\(k\)个位置，

最后还有一个\(0/1\)，如果是\(1\)，表示如果失败了还要倒着给\(g\)元。

题解

不是很难的最小割

首先很明显的，源点表示\(0\)，汇点表示\(1\)

与自己\(01\)相同的源或者汇连容量为\(0\)的边

然后往另外一侧连容量为\(v_i\)的边

先假设所有的要求都能够拿到利润

老套路的变成了计算最少的损失

如果要倒着给\(G\)元的不过是把这个任务失败的损失变成\(W_i+G\)

然后考虑怎么强行选任务

因为一个任务和其他的点之间不能断开

因此任务和其他的点用\(INF\)连接

然后这个任务要求是\(0/1\)就向对应的源/汇连容量为损失的边就行了

总的来说不是很难？？？

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 22222

#define INF 1000000000

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

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

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Line{int v,next,w;}e[3333333];

int h[MAX],cnt=2;

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

{

	e[cnt]=(Line){v,h[u],w};h[u]=cnt++;

	e[cnt]=(Line){u,h[v],0};h[v]=cnt++;

}

int level[MAX],S,T,cur[MAX];

queue<int> Q;

bool bfs()

{

	memset(level,0,sizeof(level));level[S]=1;

	while(!Q.empty())Q.pop();Q.push(S);

	while(!Q.empty())

	{

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

		for(RG int i=h[u];i;i=e[i].next)

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

			{

				level[e[i].v]=level[u]+1,Q.push(e[i].v);

				if(e[i].v==T)return true;

			}

	}

	return level[T];

}

int dfs(int u,int flow)

{

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

	int ret=0,used=0;

	for(RG int &i=cur[u];i;i=e[i].next)

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

		{

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

			used+=d;ret+=d;e[i].w-=d;e[i^1].w+=d;

			if(used==flow)return ret;

		}

	if(!ret)level[u]=0;

	return ret;

}

int Dinic()

{

	RG int ret=0;

	while(bfs())

	{

		for(RG int i=S;i<=T;++i)cur[i]=h[i];

		while(int res=dfs(S,INF))ret+=res;

	}

	return ret;

}

int a[MAX],n,m,G;

int St[MAX],top=0;

int Ans;

int main()

{

	n=read();m=read();G=read();

	for(int i=1;i<=n;++i)a[i]=read();

	S=0;T=n+m+1;

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

	{

		int x=read();

		if(a[i])Add(i,T,0),Add(S,i,x);

		else Add(i,T,x),Add(S,i,0);

	}

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

	{

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

		Ans+=W;top=read();

		for(int j=1;j<=top;++j)

		{

			int x=read();

			v?Add(i+n,x,INF):Add(x,i+n,INF);

		}

		W+=read()*G;

		v?Add(S,i+n,W):Add(i+n,T,W);

	}

	printf("%d\n",Ans-Dinic());

	return 0;

}

相关文章