牛客练习赛 小D的剑阵 解题报告

小D的剑阵

题意链接：

https://ac.nowcoder.com/acm/contest/369/F

来源：牛客网

现在你有 \(n\) 把灵剑，其中选择第i把灵剑会得到的 \(w_i\) 攻击力。

于此同时，还有 \(q\) 个约束，每个约束形如：x y v_0 v_1 v_2

\(x\) 和 \(y\) 表示两个物品的编号，如果同时选中可以获得额外 \(v_0\) 的攻击力， 同时不选可以获得额外 \(v_1\) 点攻击力，只选择一个则会扣除 \(v_2\) 的攻击力。

小D想知道剑阵的最大攻击力。

范围

\(1≤n≤10^3,0≤q≤2×10^3,2≤w_i,v_0,v_1,v_2≤7×10^4\)，且 \(w_i,v_0,v_1,v_2\) 均为偶数。

数据保证对于任一无序对\((x,y)\)只会有一个约束。

---

第一次见到类似建模，记录一下

显然是网络流。

我们先把\(w,v_0,v_1\)求和，这样就转换成了减去最小代价

考虑这样表示一个约束

考虑一个割，点被割到\(S\)表示不选，割到\(T\)表示选

然后这个基本情况有四种

• 割\(a,b\)，全选 \(a+b=v_1\)
• 割\(f,e\)，全不选 \(e+f=v_0+w_A+w_B\)
• 割\(a,c,e\)，选\(A\)，不选\(B\) \(a+c+e=v_0+v_1+v_2+w_B\)
• 割\(b,d,f\)，选\(B\)，不选\(A\) \(b+d+f=v_0+v_1+v_2+w_A\)

然后构造一种合法解进行连边

注意一下，构造中含有\(w\)的应该只连一次，所以要把含边权\(w\)的重边一起合并。

---

Code:

#include <cstdio>

#include <cstring>

#include <algorithm>

using std::min;

const int N=1e3+10;

const int M=3e4+10;

const int inf=0x3f3f3f3f;

int head[N],to[M],Next[M],edge[M],cnt=1;

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

{

	to[++cnt]=v,edge[cnt]=w,Next[cnt]=head[u],head[u]=cnt;

	to[++cnt]=u,edge[cnt]=0,Next[cnt]=head[v],head[v]=cnt;

}

int n,m,s,t,w[N],yuu[N];

int q[N],dep[N],l,r;

bool bfs()

{

	memset(dep,0,sizeof dep);

	dep[q[l=r=1]=s]=1;

	while(l<=r)

	{

		int now=q[l++];

		for(int v,i=head[now];i;i=Next[i])

			if(edge[i]&&!dep[v=to[i]])

			{

				dep[v]=dep[now]+1;

				if((q[++r]=v)==t) return true;

			}

	}

	return false;

}

int dfs(int now,int flow)

{

    if(now==t) return flow;

	int res=flow,bee;

	for(int v,i=head[now];i&&res;i=Next[i])

		if(edge[i]&&dep[v=to[i]]==dep[now]+1)

		{

			bee=dfs(v,min(res,edge[i]));

			if(!bee) {dep[v]=0;continue;}

			res-=bee,edge[i]-=bee,edge[i^1]+=bee;

		}

	return flow-res;

}

int main()

{

	scanf("%d%d",&n,&m);int ans=0;

	for(int i=1;i<=n;i++) scanf("%d",w+i),ans+=w[i];

	s=n+1,t=s+1;

	for(int x,y,v0,v1,v2,a,i=1;i<=m;i++)

	{

		scanf("%d%d%d%d%d",&x,&y,&v0,&v1,&v2);

		ans+=v0+v1;

        yuu[x]+=v1>>1,yuu[y]+=v1>>1;

        w[x]+=v0>>1,w[y]+=v0>>1;

        a=v0+v1+(v2<<1)>>1;

        add(x,y,a),add(y,x,a);

	}

	for(int i=1;i<=n;i++) add(s,i,yuu[i]),add(i,t,w[i]);

	int maxflow=0,flow;

	while(bfs()) while(flow=dfs(s,inf)) maxflow+=flow;

	printf("%d\n",ans-maxflow);

	return 0;

}

---

2019.2.16