[BZOJ3118]Orz the MST（单纯形）

2019-11-06 07:28:14

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

这题我的方法好蠢啊令xi $x_i$ 表示第i条边增加了几次，yi $y_i$ 表示第i条边减少了几次，那么目标函数就是最小化∑Ai∗xi+Bi∗yi $/sum A_i*x_i+B_i*y_i$ 然后对于每一条非树边，它的两个端点对应的树链上的每一条边都应该小于这条非树边，也就是说，xi−yi+wi≤xj−yj+wj $x_i-y_i+w_i/le x_j-y_j+w_j$ ，因为wi $w_i$ 和wj $w_j$ 的大小不定，但是Ai $A_i$ 和Bi $B_i$ 一定是正数，所以要将矩阵对偶来满足初始可行解。也就是化成xj−xi−yj+yi≤wi−wj $x_j-x_i-y_j+y_i/le w_i-w_j$ 的形式然后用单纯形解就行了但是实际上非树边只会增大，树边只会减小，所以一条边设一个未知量就行了，gg 感觉最坏情况下是可以卡成m2 $m^2$ 的啊，但是这题没有卡

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;const double eps=1e-9;const double inf=1e18;int N,M,U[1005],V[1005],W[1005],A[1005],B[1005],FF[1005];int tot,point[305],nxt[2005],v[2005],num[2005],h[205],father[305],last[305];int n,m;double a[4005][4005],b[4005],c[4005],ans;void add(int x,int y,int id){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; num[tot]=id;}void dfs(int x,int fa){ h[x]=h[fa]+1;father[x]=fa; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa) { last[v[i]]=num[i]; dfs(v[i],x); }}void build(int x,int y,int id){ int jd; // xj-xi-yj+yi<=wi-wj if (h[x]<h[y]) swap(x,y); while (h[x]>h[y]) { jd=last[x]; ++n; a[jd][n]=-1.0;a[id][n]=1.0;a[jd+M][n]=1.0;a[id+M][n]=-1.0; c[n]=W[jd]-W[id]+0.0; x=father[x]; } while (x!=y) { jd=last[x]; ++n; a[jd][n]=-1.0;a[id][n]=1.0;a[jd+M][n]=1.0;a[id+M][n]=-1.0; c[n]=W[jd]-W[id]+0.0; x=father[x]; jd=last[y]; ++n; a[jd][n]=-1.0;a[id][n]=1.0;a[jd+M][n]=1.0;a[id+M][n]=-1.0; c[n]=W[jd]-W[id]+0.0; y=father[y]; }}void pivot(int l,int e){ b[l]/=a[l][e]; for (int i=1;i<=n;++i) if (i!=e) a[l][i]/=a[l][e]; a[l][e]=1.0/a[l][e]; for (int i=1;i<=m;++i) if (i!=l&&fabs(a[i][e])>eps) { b[i]-=a[i][e]*b[l]; for (int j=1;j<=n;++j) if (j!=e) a[i][j]-=a[i][e]*a[l][j]; a[i][e]=-a[i][e]*a[l][e]; } ans+=b[l]*c[e]; for (int i=1;i<=n;++i) if (i!=e) c[i]-=c[e]*a[l][i]; c[e]=-c[e]*a[l][e];}void simplex(){ while (1) { int e; for (e=1;e<=n;++e) if (c[e]>eps) break; if (e==n+1) break; double Min=inf,t;int l; for (int i=1;i<=m;++i) if (a[i][e]>eps&&(t=b[i]/a[i][e])<Min) { Min=t; l=i; } pivot(l,e); }}int main(){ scanf("%d%d",&N,&M); for (int i=1;i<=M;++i) { scanf("%d%d%d%d%d%d",&U[i],&V[i],&W[i],&FF[i],&A[i],&B[i]); if (FF[i]) add(U[i],V[i],i),add(V[i],U[i],i); } dfs(1,0); m=M*2; for (int i=1;i<=M;++i) b[i]=A[i]+0.0,b[i+M]=B[i]+0.0; for (int i=1;i<=M;++i) if (!FF[i]) build(U[i],V[i],i); simplex(); PRintf("%.0lf/n",ans);}

上一篇：矩阵基本变换

下一篇：Leetcode-19. Remove Nth Node From End of List

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注