寒假集训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拆开,则原式会变为aiwi+bi,jwiwj\sum a_iw_i+\sum \sum b_{i,j}|w_i-w_j|

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

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

对于前面的部分,从S到i的边的流量为aiW-a_iW,从i到T的边的流量为aiWa_iW

然而流量不能为负,,,

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

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

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

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

接着考虑限制。

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

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

如果是限制wiwjw_i\le w_j,也就是当wi=Ww_i=W得时候 ,加一条从i到j的有向边,边权\infty

然后跑最大流(最小割)

完事。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
/*
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;
}
文章目录
  1. 1. 题解
|

博客使用Disqus作为评论系统