实数的线性基配用高斯消元思想食用
其实这道题是高斯消元的题
但n^3也还是可以，要在膜质数下进行
再加点贪心
#include<bits/stdc++.h> #define re return #define inc(i,l,r) for(int i=l;i<=r;++i) using namespace std; template<typename T>inline void rd(T&x) { char c;bool f=0; while((c=getchar())<'0'||c>'9')if(c=='-')f=1; x=c^48; while((c=getchar())>='0'&&c<='9')x=x*10+(c^48); if(f)x=-x; } typedef double D; D EPS=1e-4; const int maxn=505; int p[maxn]; int cost[maxn],n,m,sum,ans; inline D Fabs(D x) { re x>0?x:-x; } struct node { D x[maxn]; int cost; inline bool operator<(node c)const { re cost<c.cost; } }a[maxn]; int main() { freopen("in.txt","r",stdin); rd(n),rd(m); inc(i,1,n)inc(j,1,m) rd(a[i].x[j]); inc(i,1,n) rd(a[i].cost); sort(a+1,a+n+1);//贪心 //值域相等情况下肯定要用花费小的 inc(i,1,n) inc(j,1,m) if(Fabs(a[i].x[j])>EPS) { if(!p[j])//加入基 { p[j]=i; ++sum; ans+=a[i].cost; break; } D t=a[i].x[j]/a[p[j]].x[j];//消元 inc(k,j,m) a[i].x[k]-=a[p[j]].x[k]*t; } printf("%d %d",sum,ans); re 0; }