寒假集训1-2 variable
有 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;
}