uoj#179
#include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<cmath> #include<ctime> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<climits> #include<complex> #include<iostream> #include<algorithm> #define ll long long using namespace std; void swap(int &x,int &y){x^=y;y^=x;x^=y;} const int maxn = 50; const double eps=1e-8; const double inf=1e20; double a[maxn][maxn]; int idx[maxn],idy[maxn]; int n,m,t; void pivot(const int &e,const int &l) { double tmp=-a[l][e]; for(int i=0;i<=n;i++) if(i!=e) a[l][i]/=tmp; a[l][e]=-1/tmp; for(int i=0;i<=m;i++) { if(i==l) continue; for(int j=0;j<=n;j++) { if(j==e) continue; a[i][j]+=a[i][e]*a[l][j]; } a[i][e]*=a[l][e]; } swap(idx[e],idy[l]); } double ans[maxn]; void simplex() { for(int i=1;i<=n;i++) idx[i]=i; for(int i=1;i<=m;i++) idy[i]=n+i; int x,y; while(1) { x=y=0; for(int i=1;i<=m;i++)if(a[i][0]<-eps) {y=i;if(rand()%3==0)break;} if(!y)break; for(int i=1;i<=n;i++)if(a[y][i]>eps) {x=i;if(rand()%3==0)break;} if(!x) { printf("Infeasible\n"); return; } pivot(x,y); } while(1) { x=y=0; for(int i=1;i<=n;i++)if(a[0][i]>eps) {x=i;break;} if(!x) break; double temp=inf; for(int i=1;i<=m;i++)if(a[i][x]<-eps) { double nt=a[i][0]/-a[i][x]; if(nt<temp) { temp=nt,y=i; } } if(!y) {printf("Unbounded\n");return;} pivot(x,y); } printf("%.8lf\n",a[0][0]); if(!t) return; for(int i=1;i<=m;i++) if(idy[i]<=n) ans[idy[i]]=a[i][0]; for(int i=1;i<=n;i++) printf("%.8lf ",ans[i]); } int main() { srand(10007177); scanf("%d%d%d",&n,&m,&t); for(int i=1;i<=n;i++) scanf("%lf",&a[0][i]); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { int tmp; scanf("%d",&tmp); a[i][j]=-tmp; } int tmp; scanf("%d",&tmp); a[i][0]=tmp; } simplex(); return 0; }