锐客网

  1. 首页 > 睿知 > it技术 > >

UVA10498Happiness单纯形

IT知识Happiness单纯形

万事须己运，他得非我贤。这篇文章主要讲述UVA10498Happiness单纯形相关的知识，希望能为你提供帮助。
题目链接UVA10498
题解【UVA10498Happiness单纯形】模板题

#include< algorithm> #include< iostream> #include< cstdlib> #include< cstring> #include< cstdio> #include< vector> #include< queue> #include< cmath> #include< map> #define LL long long int #define REP(i,n) for (int i = 1; i < = (n); i++) #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt) #define cls(s,v) memset(s,v,sizeof(s)) #define mp(a,b) make_pair< int,int> (a,b) #define cp pair< int,int> using namespace std; const int maxn = 25,maxm = 100005; const double eps = 1e-12,INF = 1e15; int n,m; double a[maxn][maxn]; void Pivot(int l,int e){ double t = a[l][e]; a[l][e] = 1; for (int j = 0; j < = n; j++) a[l][j] /= t; for (int i = 0; i < = m; i++) if (l != i & & fabs(a[i][e]) > 0){ t = a[i][e]; a[i][e] = 0; for (int j = 0; j < = n; j++) a[i][j] -= a[l][j] * t; } } void simplex(){ while (true){ int l = 0,e = 0; double mn = INF; for (int j = 1; j < = n; j++) if (a[0][j] > eps){e = j; break; } if (!e) break; for (int i = 1; i < = m; i++) if (a[i][e] > eps & & a[i][0] / a[i][e] < mn) mn = a[i][0] / a[i][e],l = i; Pivot(l,e); } } int main(){ while (~scanf(" %d%d" ,& n,& m)){ REP(j,n) scanf(" %lf" ,& a[0][j]); REP(i,m){ REP(j,n) scanf(" %lf" ,& a[i][j]); scanf(" %lf" ,& a[i][0]); } a[0][0] = 0; simplex(); printf(" Nasa can spend %lld taka. " ,(LL)floor((-a[0][0]) * m + 1 - eps)); } return 0; }


    推荐阅读


    上一篇：App自动化测试必备之adb使用

    下一篇：关于SpringBoot集成myBatis时，mapper接口注入失败的问题