UVa1410/LA4027 Expensive Drink

题目链接

本题是2007年icpc亚洲区域赛北京赛区的E题

题意

你家那个调皮的小妹妹把水、牛奶、红酒混在一起，还加了点糖，打算给你喝。为了不让自己看上去太不讲理，她说如果你能猜到调制这种“混合饮料”花了多少钱，就可以逃此一劫（别告诉我你想喝它！）。调制饮料的费用等于所有原料的费用。具体来说，如果一种饮料分别用了 a1, a2, a3, a4 个单位的水、牛奶、红酒和糖，并且它们的单位价格分别为 c1,c2,c3,c4，则调制饮料的花费为 a1c1+a2c2+a3c3+a4c4。

你并不清楚这 4 样东西的市场价格是多少，但是根据常识，0≤c1≤c2≤c3。为了帮助你解决这个难题，小妹妹向你提供了这种饮料中液体的用量（即 a1,a2,a3）和另外 n（n≤100）种混合饮料的液体用量（即 a1,a2,a3）和花费。尽管所有饮料中糖的用量都是未知的，但她向你保证，在上述任何一种混合饮料中，糖的花费 a4c4 一定在区间[L,R]中。

凭借平日的了解，你断定她一定采用最贵的原料，因此你的任务是计算眼下这杯饮料的调制费用的最大值。如果她提供的信息有误，输出“Inconsistent data”；如果费用可以任意大，输出“Too expensive!”。

分析

线性规划模板题，要注意选择高效的单纯形算法模板（否则可能TLE）。另外有一个坑点：本地卡阈值，eps 推荐用1e-8。

AC 代码

#include<iostream>#include<iomanip>usingnamespacestd;#defineINF1e200#defineeps1e-8#defineM205#defineN4doublea[M][N];intB[M],C[N],m,n,L,R,kase=0;voidpivot(intr,intc){doublet=a[r][c];inte=C[c];C[c]=B[r];B[r]=e;a[r][c]=1.;for(inti=0;i<=n;++i)a[r][i]/=t;for(inti=0;i<=m;++i)if(i!=r&&abs(a[i][c])>eps){t=a[i][c];a[i][c]=0;for(intj=0;j<=n;j++)a[i][j]-=a[r][j]*t;}}boolfeasible(){while(true){intr=-1,c=-1;for(inti=0;i<m;i++)if(a[i][n]<-eps&&(r<0||(rand()&1)))r=i;if(r<0)break;for(inti=0;i<n;i++)if(a[r][i]<-eps&&(c<0||(rand()&1)))c=i;if(c<0)returnfalse;pivot(r,c);}returntrue;}intsimplex(){for(inti=0;i<n;i++)C[i]=i;for(inti=0;i<m;i++)B[i]=n+i;if(!feasible())return0;while(true){intr=-1,c=-1;doublep=INF;for(inti=0;i<n;i++)if(a[m][i]>eps){c=i;break;}if(c<0)break;for(inti=0;i<m;i++)if(a[i][c]>eps){doublev=a[i][n]/a[i][c];if(v<p)r=i,p=v;}if(r<0)return-1;pivot(r,c);}return1;}voidsolve(){cin>>L>>R;m=n+1<<1;for(inti=0;i<n;++i){for(intj=0;j<3;++j)cin>>a[i][j],a[i+n][j]=-a[i][j];intp;cin>>p;a[i][3]=p-L;a[i+n][3]=R-p;}a[m-2][0]=1.;a[m-2][1]=-1.;a[m-2][2]=a[m-2][3]=0.;a[m-1][0]=a[m-1][3]=0.;a[m-1][1]=1.;a[m-1][2]=-1.;a[m][n=3]=-R;for(inti=0;i<3;++i)cin>>a[m][i];intr=simplex();cout<<"Case "<<++kase<<": ";if(r==0)cout<<"Inconsistent data"<<endl;elseif(r<0)cout<<"Too expensive!"<<endl;elsecout<<-a[m][n]+eps<<endl;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(4);while(cin>>n&&n)solve();return0;}