BFS好题-[POI2012]BEZ-Minimalist Security-解题报告

· · 题解

给出一个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;
}