BZOJ3118 : Orz the MST
1838 ワード
ツリーエッジについては明らかに重み値を減らすだけで、非ツリーエッジについては明らかに重み値を増やすだけです.
iをツリーエッジ,jをツリーエッジとしない
X[i]:i増加量
X[j]:j減少量
C[i]:1単位iの変更の対価
各非ツリーエッジi(u,v)について、ツリー上のuからv経路上のすべてのエッジjが満たされる必要がある
$W_i+X_i\geq W_j-X_j$
すなわち
$X_i+X_j\geq W_j-W_i$
最後に$sum C_を最小化しますiX_i$
マトリックスを回転して,対偶問題を得て,線形計画単純形法で解く
iをツリーエッジ,jをツリーエッジとしない
X[i]:i増加量
X[j]:j減少量
C[i]:1単位iの変更の対価
各非ツリーエッジi(u,v)について、ツリー上のuからv経路上のすべてのエッジjが満たされる必要がある
$W_i+X_i\geq W_j-X_j$
すなわち
$X_i+X_j\geq W_j-W_i$
最後に$sum C_を最小化しますiX_i$
マトリックスを回転して,対偶問題を得て,線形計画単純形法で解く
#include<cstdio>
#define rep(i,l,n) for(int i=l;i<=n;i++)
const int N=1001,M=4000,inf=~0U>>2;
int n,m,a[N][M],nxt[M],s,t,c,nn;
int g[N],Nxt[N],v[N],ed,pre[N],id[N][N],head,tail,q[N];
inline void cal(int l,int e){
a[l][e]=-1;t=M-1;
rep(i,0,m)if(a[l][i])nxt[t]=i,t=i;nxt[t]=-1;
rep(i,0,n)if(i!=l&&(t=a[i][e])){
a[i][e]=0;
for(int j=nxt[M-1];~j;j=nxt[j])a[i][j]+=a[l][j]*t;
}
}
int work(){
for(;;){int min=inf,l=0,e=0;
rep(i,1,m)if(a[0][i]>0){e=i;break;}
if(!e)return a[0][0];
rep(i,1,n)if(a[i][e]<0&&a[i][0]<min)min=a[i][0],l=i;
cal(l,e);
}
}
struct Edge{int u,v,w,f,a,b,c;}E[N];
inline void add(int x,int y,int z){v[++ed]=y;id[x][y]=z;Nxt[ed]=g[x];g[x]=ed;}
inline void bfs(int X,int y,int z){
int i,x;
for(i=1;i<=nn;i++)pre[i]=0;
q[head=tail=0]=X;
while(head<=tail)for(i=g[x=q[head++]];i;i=Nxt[i])if(!pre[v[i]]&&v[i]!=X)pre[q[++tail]=v[i]]=x;
for(;pre[y];y=pre[y]){
++m;
i=id[y][pre[y]];
a[z][m]=a[i][m]=-1;
a[0][m]=E[i].w-E[z].w;
}
}
int main(){
scanf("%d%d",&nn,&n);
rep(i,1,n){
scanf("%d%d%d%d%d%d",&E[i].u,&E[i].v,&E[i].w,&E[i].f,&E[i].a,&E[i].b);
E[i].c=E[i].f?E[i].b:E[i].a;
if(E[i].f)add(E[i].u,E[i].v,i),add(E[i].v,E[i].u,i);
}
rep(i,1,n)if(!E[i].f)bfs(E[i].u,E[i].v,i);
rep(i,1,n)a[i][0]=E[i].c;
return printf("%d",work()),0;
}