(未完待续)实数 线性基(高斯消元)的模板题。
题目链接:Luogu P3265/LibreOJ 2108/BZOJ 4004/JLOI2015 D1T3。
题目
自己去看
题解
思路
其实就是 线性基,加个排序就行了(贪心)。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define eps 1e-6
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return res;
}
const int MAXN=500+5;
const int MAXM=500+5;
struct Node{
long double a[MAXM];
int cost;
inline bool operator<(const Node& a)const{
return cost<a.cost;
}
};
int n,m;
Node z[MAXN];
int p[MAXN];
int main(void){
n=read(),m=read();
for(reg int i=1;i<=n;++i)
for(reg int j=1;j<=m;++j)
z[i].a[j]=read();
for(reg int i=1;i<=n;++i)
z[i].cost=read();
sort(z+1,z+n+1);
reg int cnt=0,sum=0;
for(reg int i=1;i<=n;++i){
for(reg int j=1;j<=m;++j){
if(fabs(z[i].a[j])>eps){
if(!p[j]){
++cnt;
p[j]=i;
sum+=z[i].cost;
break;
}
else{
reg long double t=z[i].a[j]/z[p[j]].a[j];
for(reg int k=j;k<=m;++k)
z[i].a[k]-=t*z[p[j]].a[k];
}
}
}
}
printf("%d %d\n",cnt,sum);
return 0;
}
近期评论