P3872 [TJOI2010] 电影迷题解

pengchujie / 2023-09-03 / 原文

传送门

一眼网络流，考虑建图。

根据贪心思想，我们最好选完所有正权点，不选所有负权点。

Trick：考虑 \(S\) 向所有正权点连边，流量为权值，所有负权点向 \(T\) 连边，流量为权值绝对值。

但他还有一些限制，就是选了这个不选那个就会减少体验值，不妨设 \((x,y,z)\) 表示选了 \(x\) 不选 \(y\) 会减少 \(z\) 的体验值，考虑 \(x\) 向 \(y\) 连边，流量为 \(z\)。

Trick：当题目这样有减少体验值，可以考虑最小割

考虑割掉 \(S\) 与正权点之间连边，表示不选这个正权点，割掉 \(x->y\) 这条边表示选 \(x\) 不选 \(y\)，割掉负权点与 \(T\) 之间连边，表示选这个负权点。

最后用所有正权点的和减去最大流就好了

上代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=110000,INF=1e12;
ll n,m,a[N],s,t;
ll h[N],e[N],ne[N],w[N],idx=1;
void add(ll a,ll b,ll c)
{
	e[++idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx;
	e[++idx]=a;
	w[idx]=0;
	ne[idx]=h[b];
	h[b]=idx; 
}
ll dep[N],now[N],ans,ans1;
bool bfs()
{
	for(ll i=s;i<=t;i++) dep[i]=INF;
	dep[s]=1;
	queue<ll> q;
	q.push(s);
	now[s]=h[s];
	while(!q.empty())
	{
		ll wz=q.front();
		q.pop();
		for(ll i=h[wz];i;i=ne[i])
		{
			ll j=e[i];
			if(w[i]==0) continue;//只枚举大于0的边
			if(dep[j]==INF)
			{
				now[j]=h[j];
				dep[j]=dep[wz]+1;
				q.push(j);
				if(j==t) return true;
			}
		}
	}
	return false;
}
ll dfs(ll wz,ll k)
{
	if(wz==t) return k;
	ll sum,res=0;
	for(ll i=now[wz];i&&k;i=ne[i])
	{
		now[wz]=i;
		ll j=e[i];
		if(w[i]==0||dep[j]!=dep[wz]+1) continue;
		sum=dfs(j,min(k,w[i]));
		if(sum==0) dep[j]=INF;
		res+=sum;
		k-=sum;
		w[i]-=sum;
		w[i^1]+=sum;
	}
	return res;
}
int main()
{
	scanf("%lld %lld",&n,&m);
	s=0,t=n+1;
	for(ll i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		if(a[i]>0) add(s,i,a[i]),ans1+=a[i];
		if(a[i]<0) add(i,t,-a[i]);
	}
	ll t1,t2,t3;
	for(ll i=1;i<=m;i++)
	{
		scanf("%lld %lld %lld",&t1,&t2,&t3);
		add(t1,t2,t3);
	}
	while(bfs()) ans+=dfs(s,INF);
	printf("%lld\n",ans1-ans);
	return 0;
}