BZOJ1061: [Noi2008]志愿者招募 线性规划之--构造初始可行解
10 年前
首要思路是构造辅助线性规划,若最优值为0则删除辅助变量得到存在初始可行解线性规划.
具体看代码吧.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 | #include<cstdio>#include<cctype>#include<cstring>#include<climits>#include<iostream>#include<algorithm>using namespace std; #define inf 0x3f3f3f3fstruct Linear_Programming{ static const int N=10010; static const int M=1010; int n,m,A[M][N],b[M],c[N],v,B[M],nB[N]; int _c[N],_v,Bins[N+M],nBins[N+M],_nB[N]; inline void pivot(int l,int e){ int i,j; for(i=1;i<=n;++i) if(i!=e) A[l][i]/=A[l][e]; b[l]/=A[l][e]; A[l][e]=1/A[l][e]; for(i=1;i<=m;++i) if(i!=l&&A[i][e]!=0){ for(j=1;j<=n;++j) if(j!=e) A[i][j]-=A[i][e]*A[l][j]; b[i]-=A[i][e]*b[l]; A[i][e]*=-A[l][e]; } for(i=1;i<=n;++i) if(i!=e) c[i]-=c[e]*A[l][i]; v+=c[e]*b[l]; c[e]*=-A[l][e]; swap(B[l],nB[e]); } inline int Simplex(){ int i,j,l,e,lim; while(1){ for(e=0,i=1;i<=n;++i) if(c[i]>0){ e=i; break; } if(!e) return v; for(lim=inf,i=1;i<=m;++i) if(A[i][e]>0&&lim>b[i]/A[i][e]){ l=i; lim=b[i]/A[i][e]; } if(lim==inf) return inf; pivot(l,e); } } inline bool init(){ int i,j,l,e,min_b=inf; for(l=0,i=1;i<=m;++i) if(b[i]<min_b){ min_b=b[i]; l=i; } if(min_b>=0) return 1; nB[++n]=0; memcpy(_c,c,sizeof c); _v=v; memcpy(_nB,nB,sizeof nB); memset(c,0,sizeof c); v=0; c[n]=-1; for(i=1;i<=m;++i) A[i][n]=-1; pivot(l,n); if(Simplex()<0) return 0; else{ for(i=1;i<=m;++i) if(B[i]==0){ for(j=1;j<=n;++j){ if(A[i][j]!=0) pivot(i,j); break; } } for(i=1;i<=n;++i) if(nB[i]==0) e=i; --n; for(i=e;i<=n;++i) nB[i]=nB[i+1]; for(i=1;i<=m;++i) for(j=e;j<=n;++j) A[i][j]=A[i][j+1]; for(i=1;i<=n;++i) nBins[nB[i]]=i; for(i=1;i<=m;++i) Bins[B[i]]=i; memset(c,0,sizeof c); v=_v; for(i=1;i<=n;++i){ if(nBins[_nB[i]]) c[nBins[_nB[i]]]+=_c[i]; else{ v+=_c[i]*b[Bins[_nB[i]]]; for(j=1;j<=n;++j) c[j]-=_c[i]*A[Bins[_nB[i]]][j]; } } return 1; } }}g; int main(){ int tim,typ; cin>>tim>>typ; int i,j; for(i=1;i<=tim;++i){ scanf("%d",&g.b[i]); g.b[i]=-g.b[i]; } int s,t,c; for(i=1;i<=typ;++i){ scanf("%d%d%d",&s,&t,&c); for(j=s;j<=t;++j) g.A[j][i]=-1; g.c[i]=-c; } g.n=typ; g.m=tim; for(i=1;i<=g.n;++i) g.nB[i]=i; for(i=1;i<=g.m;++i) g.B[i]=g.n+i; g.init(); cout<<-g.Simplex()<<endl; return 0;} |
单纯形法的若干题目 BZOJ3112,3265,3550
10 年前
利用一下对偶原理建模什么的都非常裸,就放一下代码吧.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include<cstdio>#include<cstring>#include<cctype>#include<iostream>#include<algorithm>using namespace std; typedef double f2; #define INF ~0U>>1 struct Solver{ static const int N=10010;//变量个数 static const int M=1010;//限制个数 int n,m; int B[M];//基变量集合 int NB[N];//非基变量集合 f2 c[N],v;//目标函数的各项系数以及常数 f2 A[M][N],b[N];//限制的系数 Solver(){} Solver(int _n,int _m):n(_n),m(_m){} void debug(){ puts("Function"); printf("Maximize "); for(int i=1;i<=n;++i){ if(i>1)putchar('+'); printf("%.2lfx_%d",c[i],NB[i]); } printf("+%.2lf\n",v); puts("Limits"); for(int i=1;i<=m;++i){ printf("x_%d",B[i]); for(int j=1;j<=n;++j)printf("+%.2lfx_%d",A[i][j],NB[j]); printf("<=%.2lf\n",b[i]); } } inline void pivot(int l,int e){//转轴操作,将第l个基变量与第e个非基变量进行交换 int i,j,k; //更改第l个限制,得到x_e与x_l的关系式 b[l]/=A[l][e]; for(i=1;i<=n;++i)if(i!=e)A[l][i]/=A[l][e]; A[l][e]=1/A[l][e]; //将x_e带入,更改剩余的所有限制 for(i=1;i<=m;++i)if(i!=l&&A[i][e]!=0){ b[i]-=b[l]*A[i][e]; for(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]; } //更改目标函数 v+=c[e]*b[l]; for(i=1;i<=n;++i)if(i!=e)c[i]-=c[e]*A[l][i]; c[e]=-c[e]*A[l][e]; swap(B[l],NB[e]); } inline f2 solve(){//得到线性规划的最优解,或者返回无界区域 int i,j,l,e,lim; while(1){ for(e=0,i=1;i<=n;++i)if(c[i]>0){e=i;break;}//寻找最小标号的可行非基变量 if(e==0)return v;//如果不存在这样的非基变量,则已经是最优解,直接返回 //寻找最紧的上界 for(lim=INF,i=1;i<=m;++i)if(A[i][e]>0&&lim>b[i]/A[i][e])l=i,lim=b[i]/A[i][e]; if(lim==INF)return INF;//没有限制,返回无界区域 else pivot(l,e);//否则进行转轴操作 } }}Complex; void output(){Complex.debug();} int n,m;int main(){ scanf("%d%d",&n,&m); register int i,j; Complex.n=m,Complex.m=n; int x; for(i=1;i<=n;++i)scanf("%d",&x),Complex.b[i]=x; int l,r; for(i=1;i<=m;++i){ scanf("%d%d%d",&l,&r,&x); for(j=l;j<=r;++j)Complex.A[j][i]=1; Complex.c[i]=x; } for(i=1;i<=Complex.n;++i)Complex.NB[i]=i; for(i=1;i<=Complex.m;++i)Complex.B[i]=Complex.n+i; //Complex.debug(); printf("%d",(int)Complex.solve()); return 0;} |
233剩下的两道题目也很类似.