「湖南雅礼培训 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$的边已有负权，故需要依靠原图是二分图才能解决。

---

代码

#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;
}