自动搬运

查看原文

来自洛谷，原作者为

	i207M 这个家伙很蠢，什么也没有留下

搬运于2025-08-24 21:50:02，当前版本为作者最后更新于2018-11-01 14:50:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给出一个N个顶点、M条边的无向图，边(u,v)有权值w(u,v)，顶点i也有权值p(i)，并且对于每条边(u,v)都满足p(u)+p(v)>=w(u,v)。

现在要将顶点i的权值减去z(i)，其中0<=z(i)<=p(i)。修改后设顶点i的权值p'(i)=p(i)-z(i)，对于每条边(u,v)都满足p'(u)+p'(v)=w(u,v)。求sum{z(i)}的最小值和最大值。

看到式子就自己动手推一推

我们可以得到这样的式子：$z(u)+z(v)=p(u)+p(v)-w(u,v)$，观察这样的式子，我们发现，只要确定联通块内的任意一点的权值，整个联通块每个点的权值就都确定了，而最终的答案一定与那个点的权值成正比，设那个点的权值为x，最终答案一定在x取到极值时最优；

我们可以通过BFS求出每个点的权值关于x的表达式，如果是一棵树那么很简单，但是对于图，我们要讨论一下：对于偶环，式子的符号一样，必须常数也一样；对于奇环，符号不一样，我们可以解出来这个x，这是唯一可能的x，代入验证；

如何求得x的极值：我们有若干个$ax+b>=0,ax+b<=p$的限制，解这个不等式组即可；

还有一种偷懒的办法：二分$l,r$，当x最小时，应该满足$x+b>=0,-x+b<=p$的限制；当x最大时，应该满足$x+b<=p,-x+b>=0$的限制；

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<cstring>
#include<string>
#include<bitset>
#include<iomanip>
using namespace std;
#define ri register int
#define il inline
#define pb push_back
#define LL long long
#define pairint pair<int,int>
#define fi first
#define se second
#define mp make_pair

namespace i207M
{

template<class T>il void in(T &x)
{
    x=0; bool f=0; char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=1;
        c=getchar();
    }
    while(c>='0'&&c<='9') x=x*10+(c^'0'),c=getchar();
    if(f) x=-x;
}

#define N 500005
#define M 6000005
int n,m;
int vp[N];
int v[M],nx[M];
int w[M];
int head[N],cnte;
il void adde(int uu,int vv,int ww)
{
	v[++cnte]=vv,nx[cnte]=head[uu],head[uu]=cnte,w[cnte]=ww;
}
bool jud[N];
int vis[N],cur;
LL mxval,mnval;
il void gun()
{
	puts("NIE");
	exit(0);
}
struct Node
{
	LL a,b;
	Node(){ }
	Node(LL aa,LL bb)
	{
		a=aa,b=bb;
	}
	LL calc(LL x)
	{
		return a*x+b;
	}
	friend Node operator-(const Node &x,const Node &y)
	{
		return Node(x.a-y.a,x.b-y.b);
	}
};
int q[N],hd,tl;
Node zt[N];
LL zp[N];
LL calc(int st,LL dt)
{
	++cur;
	q[hd=tl=1]=st, vis[st]=cur;
	zp[st]=dt;
	LL res=0;
	while(hd<=tl)
	{
		int x=q[hd++];
		jud[x]=1;
		if(zp[x]<0||zp[x]>vp[x]) gun();
		res+=zp[x];
		for(ri i=head[x];i;i=nx[i])
		{
			LL tmp=vp[x]+vp[v[i]]-w[i]-zp[x];
			if(vis[v[i]]!=cur)
			{
				vis[v[i]]=cur,zp[v[i]]=tmp;
				q[++tl]=v[i];
			}
			else if(zp[v[i]]!=tmp) gun();
		}
	}
	return res;
}
int fa[N];
void solve(int st)
{
	++cur;
	q[hd=tl=1]=st, vis[st]=cur;
	zt[st]=Node(1,0);
	LL l=0,r=vp[st];
	while(hd<=tl)
	{
		int x=q[hd++];
		if(zt[x].a==1)
		{
			l=max(l,-zt[x].b);
			r=min(r,vp[x]-zt[x].b);
		}
		else 
		{
			l=max(l,zt[x].b-vp[x]);
			r=min(r,zt[x].b);
		}
		if(l>r) gun();
		for(ri i=head[x];i;i=nx[i])
			if(vis[v[i]]!=cur)
			{
				fa[v[i]]=x;
				vis[v[i]]=cur;
				zt[v[i]]=Node(0,vp[x]+vp[v[i]]-w[i])-zt[x];
				q[++tl]=v[i];
			}
			else if(v[i]!=fa[x])
			{
				Node t=Node(0,vp[x]+vp[v[i]]-w[i])-zt[x];
				if(zt[v[i]].a!=t.a)
				{
					LL tmp=(t.a==1?zt[v[i]].b-t.b:t.b-zt[v[i]].b);
					if(tmp%2==1) gun();
					else 
					{
						tmp=calc(st,tmp/2);
						mxval+=tmp,mnval+=tmp;
						return;
					}
				}
				else if(zt[v[i]].b!=t.b) gun();
			}
	}
	LL v1=calc(st,l),v2=calc(st,r);
	mxval+=max(v1,v2),mnval+=min(v1,v2);
}
signed main()
{
#ifdef M207
	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
#endif
	in(n),in(m);
	for(ri i=1;i<=n;++i) in(vp[i]);
	for(ri i=1,a,b,c;i<=m;++i)
	{
		in(a),in(b),in(c);
		adde(a,b,c); adde(b,a,c);
	}
	for(ri i=1;i<=n;++i)
		if(!jud[i]) 
		{
			solve(i);
		}
	printf("%lld %lld\n",mnval,mxval);
    return 0;
}

}

int main()
{
    i207M::main();
    return 0;
}