来自"NOCOW"

现在需要买n个向量。先将所有的向量按价格从小到大排序，最开始S为空集，按照这个顺序如果一个向量v能加入S（即S并上v后，仍然是线性无关）那么将v加入S，否则就不加入并且以后不再考虑v了。直到|s|=n。

说的通俗一点就是，若已确定前k个，设当前价值最小的那个n维向量是a0，若这k+1个线性无关，则加入a0,否则不再考虑a0。

再精简一点，排好序的向量，按顺序扫过去，能加入则加入，不能加入就不加入。

判断是不是线性无关可以用高斯消元（判断有没有多解即可，因为全为0肯定是一个解，如果有多解的话肯定有一个解不全为0 ）。

PS：对向量 x1,x2…xn如果存在不全为0的实数a1,…an满足a1*x1+a2*x2 …. + an*xn=0，就说它们是线性相关的，否则就是线性无关的。

下面给出两种证明（可能有很多BUG，发现的话请及时联系我）.

第一种

设p=(所有向量,线性无关的向量的集合).那么我们可以证明p是一个拟阵（又称矩阵胚，matroid）

1）它给出的向量是有限的

2）显然，所有的线性无关的向量是可以遗传的，即线性无关的向量的的任意子集也是线性无关

3）它有交换性。

所以p是拟阵。

第三点证明比较麻烦，（我用反证法做的，也不知道对不对，所以不写出来），有兴趣的可以到网上去搜以下。

由于p是拟阵，这道题便转化成了求P的最优独立集。我们可以用这种贪心的方法解决（为什么可以贪心，证明详见《算法导论第二版》P238）。

第二种

设当前处理到了第v个向量，前面已经确定了有k个向量，如果当前，v加入后会使之变成线性相关，设v=b1*a1+b2*a2+…+bk*ak，假设b1 b2 … bk中间有p个非0，设为b1, b2,… bp，那么a1, a2, .. , ap , v这p+1个向量中只要去掉一个就能使之线性无关，去掉哪一个呢？ 肯定去掉v！因为a1, a2, .. , ap , v这p+1个向量中任意选p个是等价的（因为构成的线性空间相同），所以去掉哪个意义都一样，所以肯定去掉最贵的，就肯定要是v.（其实我觉得这个证明有点难懂，也写的不是很好，大致思想是用线性空间去证，希望大牛们来改进改进）。

还说一下，这道题我在Ural上WA在了第九个点(pku上可以AC），原应（好像应该）是高斯消元时精度误差，用了取模的方法，试了几个质数都过不了。

还请大牛们指教以下。到底怎么写。给的代码也是Wa在了第九个点，(I get AC at Pku,But Wa at Ural！Do not copy!)

[编辑] 此代码在Ural上只能过9个点,但是Pku上可以AC

program cao;
const
  maxn=60;
  maxm=2100;
  eps=1e-7;
  bigprime=maxlongint;
 
var
  vec:array[0..maxm,0..maxn] of longint;
  g:array[0..maxn,0..maxn] of extended;
  order,price,used:array[0..maxm] of longint;
  buy:array[0..maxm] of boolean;
  a,b,c,d,e,f,h,i,j,k,l,n,m,p,q,ans,tmp,count:longint;
  s:extended;
 
procedure swap(var a,b:longint);
begin
  tmp:=a;
  a:=b;
  b:=tmp;
end;
 
procedure qsort(left,right:longint);
var
  i,j,x,xx:longint;
begin
  i:=left;
  j:=right;
  x:=price[(i+j) shr 1];
  xx:=order[(i+j) shr 1];
  while i<=j do
  begin
    while (price[i]<x)or((price[i]=x)and(order[i]<xx)) do inc(i);
    while (price[j]>x)or((price[j]=x)and(order[j]>xx)) do dec(j);
    if i<=j then
    begin
      swap(price[i],price[j]);
      swap(order[i],order[j]);
      move(vec[i],vec[0],sizeof(longint)*(n+1));
      move(vec[j],vec[i],sizeof(longint)*(n+1));
      move(vec[0],vec[j],sizeof(longint)*(n+1));
      inc(i);
      dec(j);
    end;
  end;
  if i<right then qsort(i,right);
  if j>left then qsort(left,j);
end;
 
procedure init;
begin
  read(m,n);
  for i:=1 to m do
  begin
    for j:=1 to n do
      read(vec[i,j]);
    order[i]:=i;
  end;
  for i:=1 to m do
    read(price[i]);
end;
 
function gauss:boolean;
var
  i,j,k:longint;
begin
  for i:=1 to count+1 do
  begin
    for j:=i to n+1 do
      if g[j,i]>eps then break;
    if j=n+1 then exit(false);
    if j<>i then
    begin
      move(g[i],g[0],sizeof(extended)*(n+1));
      move(g[j],g[i],sizeof(extended)*(n+1));
      move(g[0],g[j],sizeof(extended)*(n+1));
    end;
    for j:=1 to n do
      if j<>i then
        begin
          s:=-g[j,i]/g[i,i];
          for k:=1 to n do
            g[j,k]:=g[j,k]+g[i,k]*s;
        end;
  end;
  exit(true);
end;
 
procedure main;
begin
  qsort(1,m);
  count:=0;
  ans:=0;
  for i:=1 to m do
  begin
    fillchar(g,sizeof(g),0);
    for j:=1 to count do
      for k:=1 to n do
        g[k,j]:=vec[used[j],k] mod bigprime;
    for j:=1 to n do
      g[j,count+1]:=vec[i,j] mod bigprime;
    if gauss then
    begin
      inc(count);
      inc(ans,price[i]);
      used[count]:=i;
      buy[order[i]]:=true;
      if count=n then break;
    end;
  end;
end;
 
procedure print;
begin
  if count=n then
  begin
    writeln(ans);
    for i:=1 to m do
      if buy[i] then writeln(i);
  end
  else writeln(0);
end;
 
begin
  init;
  main;
  print;
end.

---

本菜不会做这道题，可是本菜看到Ural官方论坛1041页面里有人说了一句：

“The trouble really can be in preсision.

If you use simple Gauss with type "long double" you'll always get WA.

Do calculations in long integer numbers or modulo big prime number.

If you want, i can send you some my solutions, WA 9, WA 17, AC.”

--Wecing 23:53 2010年4月17日 (CST)

---

感谢cao的解题思路，我也是这样的，只是用了取模 AC程序如下

program djy;
type
  arr=array[1..50] of longint;
const
  prime=524081;
var
  a:array[1..2000] of arr;
  b,c,use,back:array[1..2000] of longint;
  ans:array[1..50] of longint;
  buy:array[1..2000] of boolean;
  temp:arr;
  n,m,now,cost:longint;
procedure init;
var
  i,j:longint;
begin
  readln(m,n);
  for i:=1 to m do
  for j:=1 to n do
  read(a[i,j]);
  for i:=1 to m do
  read(b[i]);
end;
procedure qsort(l,r:longint);
var
  i,j,mid,num,t:longint;
begin
  i:=l;
  j:=r;
  mid:=b[(i+j) div 2];
  num:=back[(i+j) div 2];
  repeat
    while (b[i]<mid) or ((b[i]=mid) and (back[i]<num)) do i:=i+1;
    while (b[j]>mid) or ((b[j]=mid) and (back[j]>num)) do j:=j-1;
    if i<=j then
    begin
      temp:=a[i]; a[i]:=a[j]; a[j]:=temp;
      t:=b[i]; b[i]:=b[j]; b[j]:=t;
      t:=back[i]; back[i]:=back[j]; back[j]:=t;
      i:=i+1;
      j:=j-1;
    end;
  until i>j;
  if l<j then qsort(l,j);
  if i<r then qsort(i,r);
end;
procedure prepare;
var
  i:longint;
begin
  for i:=1 to m do
  back[i]:=i;
  qsort(1,m);
end;
function gcd(x,y:longint):longint;
begin
  if y=0 then gcd:=x
  else gcd:=gcd(y,x mod y);
end;
procedure del(p,q,k:longint);
var
  i,s,pp,qq:longint;
begin
  if a[q,k]=0 then exit;
  s:=gcd(a[p,k],a[q,k]);
  pp:=a[q,k] div s;
  qq:=a[p,k] div s;
  for i:=1 to n do
  a[q,i]:=(a[p,i]*pp-a[q,i]*qq) mod prime;
end;
procedure main;
var
  i,j:longint;
  check:boolean;
begin
  now:=0;
  for i:=1 to m do
  begin
    for j:=1 to now do
    del(ans[j],i,use[ans[j]]);
    check:=false;
    for j:=1 to n do
    if a[i,j]<>0 then
    begin
      check:=true;
      use[i]:=j;
      break;
    end;
    if check=true then
    begin
      now:=now+1;
      ans[now]:=i;
      buy[back[i]]:=true;
      cost:=cost+b[i];
      for j:=1 to now-1 do
      del(i,ans[j],use[i]);
      if now=n then break;
    end;
  end;
end;
procedure print;
var
  i:longint;
begin
  if now=n then
  begin
    writeln(cost);
    for i:=1 to m do
    if buy[i]=true then writeln(i);
  end
  else writeln(0);
end;
begin
  init;
  prepare;
  main;
  print;
end.