| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:用C语言0K 0MS是怎么做到的In Reply To:用C语言0K 0MS是怎么做到的 Posted by:hszhsh at 2007-09-04 20:42:58 > RT #include <cstdio> using namespace std; #define varMax 100 #define eqMax 100 #define rMax eqMax+1 #define cMax varMax+eqMax+1 typedef long double dtype; dtype table[rMax][cMax]; dtype solution[rMax]; int rId[rMax],cId[cMax]; char basic[cMax]; int N,M; int Pivot(){ int a,b; dtype c; a=b=0; for (int i=1;i<M;i++)if (basic[cId[i]]==0)if (table[0][i]<table[0][a])a=i; if (table[0][a]>0.0)return 0; for (int i=1;i<N;i++) if (table[i][a]>0.0 && solution[i]>0.0 || table[i][a]<0.0 && solution[i]<0.0){ if (b==0)b=i; else if (solution[i]/table[i][a]<solution[b]/table[b][a])b=i; } if (b==0)return -1; basic[cId[a]]=1;basic[rId[b]]=0; rId[b]=cId[a]; c=table[b][a]; for (int i=0;i<M;i++)table[b][i]=table[b][i]/c; solution[b]=solution[b]/c; for (int i=0;i<N;i++)if (i!=b){ c=table[i][a]; for (int j=0;j<M;j++)table[i][j]=table[i][j]-c*table[b][j]; solution[i]=solution[i]-c*solution[b]; } return 1; } int LPresult; void LP_core(){ while ((LPresult=Pivot())==1); } float input[varMax][eqMax],rHand[eqMax],zrow[varMax]; int vc,ec; void LP(){ N=ec+1;M=ec+vc+1; for (int i=0;i<M;i++)table[0][i]=0.0; table[0][0]=1.0; for (int i=0;i<vc;i++)table[0][i+1]=-zrow[i]; solution[0]=0.0; for (int i=1;i<N;i++){ table[i][0]=0.0; for (int j=1;j<=vc;j++)table[i][j]=input[i-1][j-1]; for (int j=vc+1;j<M;j++)table[i][j]=0.0; table[i][vc+i]=1.0; solution[i]=rHand[i-1]; } for (int i=0;i<M;i++)cId[i]=i; rId[0]=0; for (int i=1;i<N;i++)basic[rId[i]=i+M-N]=1; LP_core(); } int main() { int a,b; scanf("%d %d",&a,&b); vc=2;ec=2; zrow[0]=1;zrow[1]=1; rHand[0]=a;rHand[1]=b; input[0][0]=1.0;input[0][1]=0.0; input[1][0]=0.0;input[1][1]=1.0; LP(); printf("%d\n",int(solution[0])); getchar();getchar(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator