UVa1410/LA4027 Expensive Drink题目链接题意分析AC 代码题目链接本题是2007年icpc亚洲区域赛北京赛区的E题题意你家那个调皮的小妹妹把水、牛奶、红酒混在一起还加了点糖打算给你喝。为了不让自己看上去太不讲理她说如果你能猜到调制这种“混合饮料”花了多少钱就可以逃此一劫别告诉我你想喝它。调制饮料的费用等于所有原料的费用。具体来说如果一种饮料分别用了 a1, a2, a3, a4 个单位的水、牛奶、红酒和糖并且它们的单位价格分别为 c1,c2,c3,c4则调制饮料的花费为 a1c1a2c2a3c3a4c4。你并不清楚这 4 样东西的市场价格是多少但是根据常识0≤c1≤c2≤c3。为了帮助你解决这个难题小妹妹向你提供了这种饮料中液体的用量即 a1,a2,a3和另外 nn≤100种混合饮料的液体用量即 a1,a2,a3和花费。尽管所有饮料中糖的用量都是未知的但她向你保证在上述任何一种混合饮料中糖的花费 a4c4 一定在区间[L,R]中。凭借平日的了解你断定她一定采用最贵的原料因此你的任务是计算眼下这杯饮料的调制费用的最大值。如果她提供的信息有误输出“Inconsistent data”如果费用可以任意大输出“Too expensive!”。分析线性规划模板题要注意选择高效的单纯形算法模板否则可能TLE。另外有一个坑点本地卡阈值eps 推荐用1e-8。AC 代码#includeiostream#includeiomanipusingnamespacestd;#defineINF1e200#defineeps1e-8#defineM205#defineN4doublea[M][N];intB[M],C[N],m,n,L,R,kase0;voidpivot(intr,intc){doubleta[r][c];inteC[c];C[c]B[r];B[r]e;a[r][c]1.;for(inti0;in;i)a[r][i]/t;for(inti0;im;i)if(i!rabs(a[i][c])eps){ta[i][c];a[i][c]0;for(intj0;jn;j)a[i][j]-a[r][j]*t;}}boolfeasible(){while(true){intr-1,c-1;for(inti0;im;i)if(a[i][n]-eps(r0||(rand()1)))ri;if(r0)break;for(inti0;in;i)if(a[r][i]-eps(c0||(rand()1)))ci;if(c0)returnfalse;pivot(r,c);}returntrue;}intsimplex(){for(inti0;in;i)C[i]i;for(inti0;im;i)B[i]ni;if(!feasible())return0;while(true){intr-1,c-1;doublepINF;for(inti0;in;i)if(a[m][i]eps){ci;break;}if(c0)break;for(inti0;im;i)if(a[i][c]eps){doubleva[i][n]/a[i][c];if(vp)ri,pv;}if(r0)return-1;pivot(r,c);}return1;}voidsolve(){cinLR;mn11;for(inti0;in;i){for(intj0;j3;j)cina[i][j],a[in][j]-a[i][j];intp;cinp;a[i][3]p-L;a[in][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][n3]-R;for(inti0;i3;i)cina[m][i];intrsimplex();coutCase kase: ;if(r0)coutInconsistent dataendl;elseif(r0)coutToo expensive!endl;elsecout-a[m][n]epsendl;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);coutfixedsetprecision(4);while(cinnn)solve();return0;}