雅礼集训1.2 变量

Posted by yjjr's blog on January 1, 2018

标签:网络流,最小割,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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr