牛客练习赛 小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\)求和,这样就转换成了减去最小代价

考虑这样表示一个约束

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

考虑一个割,点被割到\(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

上一篇:Web ADF 编程步骤.


下一篇:问题在哪?动态菜单条-------Day86