首页 > 代码库 > 3118: Orz the MST（单纯形）
3118: Orz the MST（单纯形）
题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3118
题意：给出一个图以及图中指定的n-1条边组成的生成树。每条边权值加1或者减去1都有相应的代价。求一个最小代价使得给出的边是最小生成树。
思路：对于每条非树边，必与某些树边形成环。设该非树边的权值为w2,某树边的权值为 w1。最后非树边增加x2,树边减少x1，那么w1-x1<=w2+x2。这样我们可以得到一些式子。代价也知道，这样就转化成线性规划问题。题目求的是最小值，我们可以将目标方程的系数取反求最大值。
单纯形的步骤：
（1）求出一个初始解；
（2）迭代。
（1）这个题的系数矩阵A是全么模：1、元素都是0，-1，1；2、任意子方阵的行列式为0，-1,1。
（2）据说A是全么模时解是整数解，因此此题可直接用单纯形。
const int COL=1005;const int ROW=30005;int n,m,B[ROW],N[COL];double A[ROW][COL],b[ROW],c[COL],v;double ans[COL];int sgn(double x){ if(x>1e-8) return 1; if(x<-1e-8) return -1; return 0;}//B中第l个替换N中第e个void pivot(int l,int e){ int i,j; double temp=A[l][e]; b[l]/=temp; A[l][e]=1/temp; for(i=1;i<=n;i++) if(i!=e) A[l][i]/=temp; for(i=1;i<=m;i++) if(i!=l) { b[i]-=A[i][e]*b[l]; for(j=1;j<=n;j++) if(j!=e) A[i][j]-=A[i][e]*A[l][j]; A[i][e]=-A[i][e]/temp; } v+=b[l]*c[e]; for(i=1;i<=n;i++) if(i!=e) c[i]-=c[e]*A[l][i]; c[e]*=-A[l][e]; swap(B[l],N[e]);}void simplex(){ int i,j,k,x; int l,s; double temp,temp1,temp2,temp3; while(1) { temp2=-dinf; s=-1; for(i=1;i<=n;i++) if(sgn(c[i])>0) { temp=dinf; for(k=1;k<=m;k++) if(sgn(A[k][i])>0) { temp3=b[k]/A[k][i]; if(temp3<temp) temp=temp3,x=k; } if(temp2<temp*c[i]) { s=i,l=x,temp2=temp*c[i]; } } if(s==-1) break; pivot(l,s); } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) if(B[j]==i) break; if(j<=m) ans[i]=b[j]; else ans[i]=0; }}void print(){ int i,j; printf("v: %.3lf\n",v); printf("c:\n"); for(i=1;i<=n;i++) printf("%.3lf ",c[i]); puts(""); printf("A:\n"); for(i=1;i<=m;i++) { for(j=1;j<=n;j++) printf("%.3lf ",A[i][j]); puts(""); } printf("b:\n"); for(i=1;i<=m;i++) printf("%.3lf ",b[i]); puts(""); printf("B:\n"); for(i=1;i<=m;i++) printf("%d ",B[i]); puts(""); printf("N:\n"); for(i=1;i<=n;i++) printf("%d ",N[i]); puts("");}int init(){ int i,j; int k=1; for(i=1;i<=m;i++) if(b[i]<b[k]) k=i; if(sgn(b[k])>=0) { for(i=1;i<=n;i++) N[i]=i; for(i=1;i<=m;i++) B[i]=n+i; v=0; simplex(); return 1; } static double tmpC[COL]; for(i=1;i<=n;i++) tmpC[i]=c[i]; tmpC[n+1]=0; n++; for(i=1;i<=m;i++) A[i][n]=-1; for(i=1;i<=n;i++) N[i]=i; for(i=1;i<=m;i++) B[i]=n+i; v=0; for(i=1;i<=n;i++) { if(i<n) c[i]=0; else c[i]=-1; } pivot(k,n); simplex(); if(sgn(ans[n])!=0) return 0; static int belongB[COL]; clr(belongB,0); for(i=1;i<=m;i++) { if(B[i]>n) continue; belongB[B[i]]=i; } map<int,int> mp; for(i=1;i<=n;i++) mp[N[i]]=i; clr(c,0); v=0; for(i=1;i<=n;i++) { if(!belongB[i]) { c[mp[i]]+=tmpC[i]; } else { v+=tmpC[i]*b[belongB[i]]; int j; for(j=1;j<=n;j++) { c[j]+=tmpC[i]*(-A[belongB[i]][j]); } } } c[mp[n]]=0; for(i=1;i<=m;i++) A[i][mp[n]]=0; simplex(); n--; return 1;}struct node{ int u,v,id,w,next;};node edges[ROW];int e;int head[COL];void add(int u,int v,int w,int id){ e++; edges[e].u=u; edges[e].v=v; edges[e].w=w; edges[e].id=id; edges[e].next=head[u]; head[u]=e;}int h[COL],up[COL],down[COL];int eNum;int inq[COL],KK;int pre[COL];void build(int s,int t,int p){ int i; for(i=pre[t];i!=-1;) { int w1=edges[i].w; int w2=edges[p*2].w; m++; A[m][edges[i].id]=-1; A[m][p]=-1; b[m]=w2-w1; int u=edges[i].u; i=pre[u]; }}void bfs(int s,int t,int p){ queue<int> Q; Q.push(s); KK++; inq[s]=KK; pre[s]=-1; while(!Q.empty()) { int u=Q.front(); Q.pop(); int i; for(i=head[u];i!=-1;i=edges[i].next) { int v=edges[i].v; int id=edges[i].id; if(!h[id]||KK==inq[v]) continue; pre[v]=i; if(v==t) { build(s,t,p); return; } Q.push(v); inq[v]=KK; } }}int main(){ n=myInt(); eNum=myInt(); clr(head,-1); int i; for(i=1;i<=eNum;i++) { int u,v,w; scanf("%d%d%d%d%d%d",&u,&v,&w,&h[i],&up[i],&down[i]); add(u,v,w,i); add(v,u,w,i); } for(i=1;i<=eNum;i++) if(!h[i]) { int t=i*2; bfs(edges[t].u,edges[t].v,i); } for(i=1;i<=eNum;i++) c[i]=h[i]?-down[i]:-up[i]; n=eNum; if(!init()) { puts("no solution"); } double res=-v; if(res<1e-10) res=0; printf("%.0lf\n",-v);}
3118: Orz the MST（单纯形）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。