「湖南雅礼培训 1.2」变量 - 网络流+离散变量模型 | Bill Yang's Blog
0%

「湖南雅礼培训 1.2」变量 - 网络流+离散变量模型

题目大意

    有$n$个变量$w[1]\sim w[n]$,每个变量可以取$W$或$-W$。
    有$p$个式子,形如$H_i=a_i\left|w[x_i]-w[y_i]\right|+b_i\left|w[y_i]-w[z_i]\right|+c_i\left|w[z_i]-w[x_i]\right|+d_i(w[x_i]-w[y_i])+e_i(w[y_i]-w[z_i])+f_i(w[z_i]-w[x_i])$。
    有$q$个条件,形如$w[x]\le w[y]$或$w[x]=w[y]$或$w[x]\lt w[y]$。
    最小化$\sum(w_i)+\sum(H_i)$。


题目分析

经典离散变量模型。
从源点$S$向$i$结点连边,割掉这条边表示选择$W$,$i$向$T$连边,割掉表示选择$-W$。

考虑限制条件。

发现$w[x]\le w[y]$的限制可转化为连一条$y\rightarrow x$的边。
$w[x]=w[y]$可转化为$w[x]\le w[y],w[y]\le w[x]$。
$w[x]\lt w[y]$可转化为$w[x]=-W,w[y]=W$,从源点和汇点分别连边。

考虑$p$个式子。
首先不带绝对值的$d_i(w[x_i]-w[y_i])+e_i(w[y_i]-w[z_i])+f_i(w[z_i]-w[x_i])$直接拆开记为$S\rightarrow i\rightarrow T$的边权。
带绝对值的$a_i\left|w[x_i]-w[y_i]\right|+b_i\left|w[y_i]-w[z_i]\right|+c_i\left|w[z_i]-w[x_i]\right|$,考虑当且仅当绝对值内部值选择不同才会产生$2W$的权值,记为$x\leftrightarrow y$的边权。

容量带有负权,统一加上偏移量计算。

如果绝对值内部$-$号改为$+$号,使用二元组分析发现$x\leftrightarrow y$的边权为负,需要偏移量,而原本$S\rightarrow i\rightarrow T$的边已有负权,故需要依靠原图是二分图才能解决。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=2005;

struct Edge {
int from,to,cap,flow;
Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};

struct Dinic {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool vst[maxn];
int dist[maxn],cur[maxn];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v) {
edges.push_back(Edge(x,y,v,0));
edges.push_back(Edge(y,x,0,0));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bfs() {
memset(vst,0,sizeof(vst));
memset(dist,0,sizeof(dist));
queue<int>Q;
Q.push(t);
vst[t]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(!vst[Next]&&e.cap>e.flow) {
vst[Next]=1;
dist[Next]=dist[Now]+1;
Q.push(Next);
}
}
}
return vst[s];
}
int dfs(int Now,int a) {
if(Now==t||a==0)return a;
int flow=0;
for(int& i=cur[Now]; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(dist[Now]-1!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
e.flow+=nextflow;
edges[G[Now][i]^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
int flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} dinic;

int n,w,p,q,val[maxn],map[maxn][maxn];

int main() {
int t=Get_Int();
while(t--) {
n=Get_Int();
w=Get_Int();
p=Get_Int();
q=Get_Int();
memset(map,0,sizeof(map));
for(int i=1; i<=n; i++)val[i]=1;
for(int i=1; i<=p; i++) {
int x=Get_Int(),y=Get_Int(),z=Get_Int(),a=Get_Int(),b=Get_Int(),c=Get_Int(),d=Get_Int(),e=Get_Int(),f=Get_Int();
val[x]+=d-f;
val[y]+=e-d;
val[z]+=f-e;
map[x][y]+=a,map[y][x]+=a;
map[y][z]+=b,map[z][y]+=b;
map[x][z]+=c,map[z][x]+=c;
}
int Max=0,S=n+1,T=n+2;
for(int i=1; i<=n; i++)Max=max(Max,abs(val[i])+1);
dinic.init(T);
for(int i=1; i<=n; i++) {
dinic.AddEdge(S,i,Max+val[i]);
dinic.AddEdge(i,T,Max-val[i]);
}
int cnt=T;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
if(map[i][j]==0)continue;
dinic.AddEdge(i,j,2*map[i][j]);
}
for(int i=1; i<=q; i++) {
int x=Get_Int(),y=Get_Int(),z=Get_Int();
if(z==0)dinic.AddEdge(y,x,INT_MAX);
else if(z==1)dinic.AddEdge(x,y,INT_MAX),dinic.AddEdge(y,x,INT_MAX);
else if(z==2)dinic.AddEdge(S,x,INT_MAX),dinic.AddEdge(y,T,INT_MAX);
}
printf("%lld\n",1ll*(dinic.maxflow(S,T)-Max*n)*w);
}
return 0;
}
姥爷们赏瓶冰阔落吧~