Problem

https://www.luogu.org/problemnew/show/P3265

Solution

考虑一组 $k$ 维向量。

我们可以对向量定义一个乘上标量的操作。
我们再定义一个向量与向量相加的操作。
由这两种操作，对于某组向量里，有一些向量可以用其它的向量得到，那么这组向量就是多余的。

现在我们有这组向量，我们需要找到最精简的向量组，通过这两种操作能够得到这组向量里的所有向量。
那么这个向量组就叫基。

我们考虑我们需要的基是个什么东西。

我们需要的基是一个这样的 $k*k$ 的矩阵。

性质：对于第 $i$ 行矩阵，$a_{i,i}=1$，而对于所有的 $a_{i, j}=0,\ j< i$。每一行代表了基里的一组向量。
那么我们如果对这个矩阵进行一下高斯消元，一定可以化成对角线为 1 的形式，即能表示所有的向量。

所以基里的向量组最多是 $k$ 组，且基里的向量一定不能互相表示（即线性无关）。

我们考虑怎么得到这个基。
维数从小到大往基里插入这个向量。若这个向量的第 $i$ 维不为 0，而基里的第 $i$ 行的第 $i$ 维不为 0。那么我们可以用基里的这个向量来消去插入的向量的该维，并向下检查。若为 0，则往基里插入这组向量。这组向量保证了是通过之前所给的向量组运算而来的，并且符合基的要求，因此可以成为基里的一组向量。

如果插到最后都找不到，就说明这组向量能被现有基里的向量所表示。

基里的所有向量都由原本的向量组运算而来，并且通过运算去除了冗余的向量，因此通过基里的向量互相运算，一定能够展开成原来向量组（生成基的逆运算）。

无论是对于异或线性基（一个数是 32/64 维的向量组），还是这样的实数线性基，原理都是一样的。

建议结合异或线性基来进行更好的理解。

对于本题，维护一个实数线性基。
基里含有的线性基的个数是确定的。因为经过高斯消元整理过后的基一定是唯一的。
因此影响的实际上是插入线性基的顺序。

一个贪心的思想，花费小的先插入线性基，肯定没错就是了 emm

UPD

很有意思的是这个贪心的问题与 kruskal 非常类似，于是我在想 kruskal 的正确性。

我们假设现在我们选择序列中的四个元素，这四个元素的权值从小到大排列。

若我们按照贪心策略选择，有 $A< B< C< D$，选择 $A,D$。则存在选择 $A$ 则不能选择 $B,C$，否则不会选到 $D$。

若我们需要选择 $B$，则存在不选择 $A$ 能选择 $B$。

则这要求我们一定选择 $C$，才可能有 $B+C< A+D$。

我们考虑有连通块 $X,Y$，则有边 $X-A-Y$。

选择 $A$ 不能选择 $B$，不选择 $A$ 能选择 $B$，显然有边 $X-B-Y$。

选择 $A$ 不能选择 $C$，显然存在 $C$ 处于连通块 $X,Y$ 中或 $X-C-Y$ 或其它情况。

无论哪种情况，都有选择 $B$ 不能选择 $C$。

这个问题跟其非常相似。

因为选择 $A$ 不能选择 $B,C$。则 $B$ 和 $C$ 都能被基 $S+A$ 所表示。

更加阐述一下，令 $B=S+k_1A$，则存在 $C=S'+k_2B=S'+k_2(S+k_1A)=S'+k_2S+k_2k_1A=S''+k_2k_1A$。

所以选择 $B$ 不能选择 $C$。

因此这个贪心是正确的。

~~希望我没证假~~

Code

// Code by ajcxsu
// Problem: kejin

#include<bits/stdc++.h>
#define EPS (1e-12)
using namespace std;

typedef long double ld;
const int N=510;
int n, m;
struct Basis {
    ld a[N][N];
    char vis[N];
    bool ins(ld b[]) {
        for(int i=1;i<=m;i++)
            if(fabs(b[i])>EPS){
                if(!vis[i]) { for(int j=i;j<=m;j++) a[i][j]=b[j]/b[i]; vis[i]=1; return true; }
                else for(int j=i+1;j<=m;j++) b[j]-=a[i][j]*b[i];
                b[i]=0;
            }
        return false;
    }
} bas;

struct W { int idx, c; } w[N];
bool cmp(const W &a, const W &b) { return a.c<b.c; }
ld b[N][N];
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n>>m;
    int cnt=0, cost=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) cin>>b[i][j];
    for(int i=1;i<=n;i++) cin>>w[i].c, w[i].idx=i;
    sort(w+1, w+1+n, cmp);
    for(int i=1;i<=n;i++)
        if(bas.ins(b[w[i].idx]))
            cnt++, cost+=w[i].c;
    cout<<cnt<<' '<<cost<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3265.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议进行许可☆

网站

加入讨论吧...