题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4004
数据生成器:http://paste.ubuntu.com/23209631/
这个题目,看一眼,就是要求一组花费最小的线性基
第一次写,写的整数高斯消元,发现爆了long long
第二次改成double,发现精度不够
第三次,搞成整数高斯消元+MOD,遂过之
想一想,如果不用线性基,只是求一组线性基的话,MOD确实没影响
另外网上用double写的标程全部被叉掉了,不要问我是怎么知道的 qwq
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 500+9; const int MOD = 1000000007; int n,m,f[N][N],bas[N],cost[N],num[N],cnt,vout; inline int read(){char c=getchar(); int ret=0,f=1;while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret*f;} inline bool cmp(const int a, const int b) {return cost[a] < cost[b];} inline void update(int w) { for (int i=1;i<=m;i++) if (f[w][i]) { if (!bas[i]) {bas[i] = w, cnt++, vout += cost[w]; break;} else { int t2 = f[bas[i]][i], t1 = f[w][i]; for (int j=1;j<=m;j++) f[w][j] = ((LL)f[w][j]*t2 - (LL)f[bas[i]][j]*t1) % MOD; } } } int main(){ n = read(); m = read(); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) f[i][j] = read(); for (int i=1;i<=n;i++) cost[i] = read(), num[i] = i; sort(num+1,num+1+n,cmp); for (int i=1;i<=n;i++) update(num[i]); printf("%d %d\n",cnt,vout); return 0; }
As I site possessor I believe the content material here is rattling great , appreciate it for your hard work. You should keep it up forever! Good Luck.
Spot on with this write-up, I really suppose this web site wants far more consideration. I’ll probably be once more to read far more, thanks for that info.