有 n 个变量 w[1]~w[n],每个变量可以取 W 或-W。
有 p 个式子,形如 Hi=ai|w[xi]-w[yi]|+bi|w[yi]-w[zi]|+ci|w[zi]-w[xi]|
+di(w[xi]-w[yi])+ei(w[yi]-w[zi])+fi(w[zi]-w[xi])。
有 q 个条件,形如 w[x]<=w[y]或 w[x]=w[y]或 w[x]<w[y]。
最小化 sigma(wi)+sigma(Hi)。

题解

网络流。

建源点S，汇点T和n个点1..n。

把Hi拆开，则原式会变为$\sum a_iw_i+\sum \sum b_{i,j}|w_i-w_j|$

首先从S到1..n,1..n到T各连一条边，割从S到i的边表示$w_i=-W$，割从i到T的边表示$w_i=W$

对于后面的绝对值部分，显然当$w_i≠w_j$时，得到的结果要$+2b_{i,j}w$，于是连一条流量为$2b_{i,j}$从i到j的双向边。

对于前面的部分，从S到i的边的流量为$-a_iW$，从i到T的边的流量为$a_iW$。

然而流量不能为负，，，

考虑默认割掉流量负的边，并把答案加上。

但是如果要割正边怎么办呢？

那就把对应边先减去这条边的边权（也就是*2），然后如果割了那条边就相当于没割这条边了。

然后这条边就可以不用加了。

接着考虑限制。

如果是限制$w_i<w_j$，相当于强制限定$w_i,w_j$，加上从S到i，从j到T的有向边，流量$\infty$。

如果是限制$w_i=w_j$，那就是说要么都$>0$，要么都$<0$，连一条从i到j的无向边，流量$\infty$

如果是限制$w_i\le w_j$，也就是当$w_i=W$得时候$w_j\not= -W$，加一条从i到j的有向边，边权$\infty$

然后跑最大流（最小割）

完事。

/*
Author: CNYALI_LK
LANG: C++
PROG: variable.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
    ll s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
    ll cnt=0,fu=1;
    if(a<0){putchar('-');fu=-1;}
    do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
    while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
    putchar(end);
}
#ifndef cnyali_lk
#define cnyali_lk
#endif
namespace NetWorkFlow{
    ll n;
    ll beg[102424],to[204848],lst[204848],w[204848],e;
    void clear(ll m){
        n=m+2;
        e=1;
        for(ll i=1;i<=n;++i)beg[i]=0;
    }
    void Add(ll u,ll v,ll W){
        to[++e]=v;
        lst[e]=beg[u];
        beg[u]=e;
        w[e]=W;
    }
    void NewEdge(ll u,ll v,ll w){

        ++u;++v;
        Add(u,v,w);
        Add(v,u,0);
    }
    ll dis[102424],flow[102424],gap[102424],q[102424],cur[102424],back[102424];
#define C cur[now]
    void bfs(){
        for(ll i=1;i<=n;++i)dis[i]=n,gap[i]=0,cur[i]=beg[i];
        ll l,r,s;
        q[l=r=1]=n;
        gap[dis[n]=0]=1;
        while(l<=r){
            s=q[l];
            for(ll i=beg[s];i;i=lst[i]){
                if(!w[i]&&dis[to[i]]==n){
                    dis[to[i]]=dis[s]+1;
                    ++gap[dis[to[i]]];
                    q[++r]=to[i];
                }
            }
            ++l;
        }
    }

    ll iSap(){
        ll s=1,t=n,now=1,nxt,ans=0;
        bfs();
        flow[s]=0x3f3f3f3f;
        back[s]=0;
        while(dis[s]!=n){
            nxt=0;
            for(;C; C=lst[C])if(w[C]&&dis[now]==dis[to[C]]+1){
                nxt=to[C];
                break;
            }
            if(nxt){
                flow[nxt]=min(flow[now],w[C]);
                back[nxt]=now;
                if(nxt==t){
                    ans+=flow[nxt];
                    while(now){
                        w[C]-=flow[nxt];
                        w[C^1]+=flow[nxt];
                        now=back[now];
                    }
                    now=s;
                }
                else now=nxt;
            }
            else{
                if(!--gap[dis[now]])return ans; 
                dis[now]=n;
                C=beg[now];
                for(ll i=beg[now];i;i=lst[i])if(w[i])chkmin(dis[now],dis[to[i]]+1);
                ++gap[dis[now]];
                if(back[now])now=back[now];
            }
        }
        return ans;
    }
};
using NetWorkFlow::clear;
using NetWorkFlow::NewEdge;
using NetWorkFlow::iSap;
ll s[102424];
int main(){
#ifdef cnyali_lk
    freopen("variable.in","r",stdin);
    freopen("variable.out","w",stdout);
#endif
    ll n,t,w,p,q,x,y,z,a,b,c;
    t=read();
    while(t){
        --t;
        n=read();
        w=read();p=read();q=read();
        clear(n);
        for(ll i=1;i<=n;++i){
            s[i]=1; 
        }
        for(ll i=1;i<=p;++i){
            x=read();y=read();z=read();

            a=read();b=read();c=read();
            a<<=1;b<<=1;c<<=1;
            NewEdge(x,y,a);
            NewEdge(y,x,a);
            NewEdge(y,z,b);
            NewEdge(z,y,b);
            NewEdge(x,z,c);
            NewEdge(z,x,c);
            a=read();b=read();c=read();
            s[x]+=a-c;
            s[y]+=b-a;
            s[z]+=c-b;
        }
        for(ll i=1;i<=q;++i){
            x=read();y=read();z=read();
            if(!z)NewEdge(x,y,0x3f3f3f3f);
            else if(z==1)NewEdge(x,y,0x3f3f3f3f),NewEdge(y,x,0x3f3f3f3f);
            else {
                NewEdge(x,n+1,0x3f3f3f3f);
                NewEdge(0,y,0x3f3f3f3f);
            }
        }
        ll ans=0;
        for(ll i=1;i<=n;++i){
            ans-=abs(s[i]);
            if(s[i]<0){NewEdge(0,i,(-2*s[i]));}
            else NewEdge(i,n+1,2*s[i]);
        }
        ans+=iSap();
        printf("%lld\n",ans*w);
    }

    return 0;
}

标签: 网络流

添加新评论