标签：网络流，最小割，dinic
题目
变量（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)。 【输入数据】 第一行一个整数 t 表示数据组数。 每组数据第一行四个整数 n,W,p,q 表示节点数。 接下来 p 行每行九个整数 xi,yi,zi,ai,bi,ci,di,ei,fi。 接下来 q 行每行三个整数 x,y,r。 r=0 表示 w[x]<=w[y]；r=1 表示 w[x]=w[y]；r=2 表示 w[x] < w[y]。 保证存在方案。 【输出数据】 每组数据输出一行一个整数表示 sigma(wi)+sigma(Hi)的最小值。 【样例输入】 1 3 1 1 1 1 2 3 1 1 1 1 1 1 1 2 2 【样例输出】 3 【数据范围】 对于 30%的数据，n<=15，p,q<=20。
对于100%的数据， t<=10，n<=500，p,q<=1000，1<=W<=10^6， 0<=ai,bi,ci,di,ei,fi<=1000。
分析
考试的时候打暴力qwq
虽然大家都一眼看出来了是网络流
坐我对面的小哥哥硬肝了这题3h+，依然不会建图
建图：
将每个点i拆成两个点（i,i+n）
S向每个点i建一条权值为W的边，i+n向汇点T建一条权值为-W的边
对于xi*wi讨论正负，向其中一条边上加权值
对于$xiabs(w[a[i]]-w[b[i]])$，在a[i]和b[i]之间连权值为2xi的边
对于限制：
- 当r=0时，建一条从y向x的有向边（权值为inf）
- 当r=1时，建一条从x向y的无向边（权值为inf）
- 当r=2时，从源点S向x连一条inf的有向边，从y向T同样连一条
然后跑最小割就可以了，好神奇的建图方式呐！
code
30分暴力（注意要开Long long）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define dep(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=26;
ll book[maxn],x[maxn],y[maxn],z[maxn],a[maxn],b[maxn],c[maxn],d[maxn],e[maxn],f[maxn],lx[maxn],ly[maxn],lr[maxn];
ll T,n,p,q,W;
bool check(){
ll t[maxn];
rep(i,1,n)if(book[i]==1)t[i]=-W;else t[i]=W;
rep(i,1,q){
if(lr[i]==0){
if(t[lx[i]]>t[ly[i]])return 0;
}if(lr[i]==1){
if(t[lx[i]]!=t[ly[i]])return 0;
}if(lr[i]==2){
if(t[lx[i]]>=t[ly[i]])return 0;
}
}
return 1;
}
ll work(){
ll t[maxn];ll sum=0;
rep(i,1,n)if(book[i]==1)t[i]=-W;else t[i]=W;
rep(i,1,n)sum+=t[i];
rep(i,1,p)sum+=(ll)(a[i]*abs(t[x[i]]-t[y[i]])+b[i]*abs(t[y[i]]-t[z[i]])+c[i]*abs(t[z[i]]-t[x[i]])
+d[i]*(t[x[i]]-t[y[i]])+e[i]*(t[y[i]]-t[z[i]])+f[i]*(t[z[i]]-t[x[i]]));
return sum;
}
int main()
{
//freopen("variable.in","r",stdin);
//freopen("variable.out","w",stdout);
T=read();
while(T--){
mem(x,0);mem(y,0);mem(z,0);mem(a,0);mem(b,0);mem(c,0);mem(d,0);mem(e,0);mem(f,0);mem(lx,0);mem(ly,0);mem(lr,0);
n=read(),W=read(),p=read(),q=read();ll pos;ll ans=1e9;
rep(i,1,p)x[i]=read(),y[i]=read(),z[i]=read(),a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read(),e[i]=read(),f[i]=read();
rep(i,1,q)lx[i]=read(),ly[i]=read(),lr[i]=read();
mem(book,0);if(check())ans=work();
while(book[n+1]==0){
rep(i,1,n+1)if(book[i]==0){pos=i;break;}
book[pos]=1;rep(i,1,pos-1)book[i]=0;
if(check())ans=min(ans,work());
//rep(i,1,n+1)cout<<book[i];cout<<' '<<check()<<' '<<work()<<' '<<endl;
}
cout<<ans<<endl;
}
return 0;
}
正解
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=506,maxm=1e4+6;
int Que,n,m,S,T,p,q,cnt=1,last[maxm],mp[maxn][maxn],val[maxn],h[maxm],que[maxm<<2],mx;
int xi,yi,zi,ai,bi,ci,di,ei,fi;
ll w,ans;
struct edge{int to,next,v;}e[maxm*10];
void insert(int u,int v,int w){
e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
e[++cnt]=(edge){u,last[v],0};last[v]=cnt;
}
bool bfs(){
int head=0,tail=1,now;mem(h,-1);
que[0]=S;h[S]=0;
while(head<tail){
now=que[head++];
reg(now)
if(h[e[i].to]==-1&&e[i].v){
h[e[i].to]=h[now]+1;
que[tail++]=e[i].to;
}
}
return h[T]!=-1;
}
int dfs(int x,int f){
if(x==T)return f;
int w,used=0;
reg(x)
if(h[e[i].to]==h[x]+1){
w=dfs(e[i].to,min(f-used,e[i].v));
e[i].v-=w;e[i^1].v+=w;used+=w;
if(used==f)return f;
}
if(!used)h[x]=-1;
return used;
}
void dinic(){while(bfs())ans+=dfs(S,inf);}
int main()
{
Que=read();
while(Que--){
n=read(),w=read(),p=read(),q=read();
mem(last,0);mem(mp,0);mem(val,0);mx=0;ans=0;
rep(i,1,n)val[i]=1;
rep(i,1,p){
xi=read(),yi=read(),zi=read(),ai=read(),bi=read(),ci=read(),di=read(),ei=read(),fi=read();
val[xi]+=di-fi;val[yi]+=ei-di;val[zi]+=fi-ei;
if(xi<yi)mp[xi][yi]+=ai;else mp[yi][xi]+=ai;
if(yi<zi)mp[yi][zi]+=bi;else mp[zi][yi]+=bi;
if(zi<xi)mp[zi][xi]+=ci;else mp[xi][zi]+=ci;
}
rep(i,1,n)mx=max(mx,abs(val[i]));mx++;
S=n<<1|1;T=S+1;
rep(i,1,n){
insert(S,i,mx+val[i]);
insert(i,i+n,inf);
insert(i+n,T,mx-val[i]);
}
rep(i,1,n)
rep(j,i+1,n){
if(mp[i][j]==0)continue;
insert(i+n,j,2*mp[i][j]);
insert(j+n,i,2*mp[i][j]);
}
rep(i,1,q){
xi=read(),yi=read(),zi=read();
if(zi==0)insert(yi+n,xi,inf);
if(zi==1){insert(xi+n,yi,inf);insert(yi+n,xi,inf);}
if(zi==2){insert(S,xi,inf);insert(yi+n,T,inf);}
}
dinic();
ans=1LL*(ans-mx*n)*w;
cout<<ans<<endl;
}
return 0;
}
