注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Ural 1041高斯消元求矩阵的秩  

2012-09-13 17:03:11|  分类: ural |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
很明显的一个贪心策略
很容易想到高斯消元
但做起来却蛋疼无比
不只是用取模替代高精度,也不只是强行将高斯消元降至n^2
更不用说只需要求矩阵的秩即可
单是忘了看到要输出字典序最小的方案,就足足耗费了好多小时
不过最终还是过了啊,对高斯消元顿时理解更深一步

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;

typedef long long LL;
const LL MAX=4000+10;
const LL MAXN=100;
const LL Mod=549979;

struct vec
{
LL cost,num;
LL c[MAXN];
}d[MAX],ans[MAX];
LL m,n,now,p[MAX],g[MAXN][MAXN],point[MAXN];

int cmp(const vec& a,const vec& b)
{
if(a.cost!=b.cost)return a.cost<b.cost;
else return a.num<b.num;
}

void swapl(int a,int b)
{
int i;
for(i=1;i<=n;++i)
swap(g[i][a],g[i][b]);
}

void elim(LL* a,LL* b,int p)
{
int i;
LL old=b[p];
for(i=1;i<=n;++i)
b[i]=(b[i]*a[p]-a[i]*old+Mod*Mod)%Mod;
}

int calc(LL& now,int id)
{
int i;
++now;
for(i=1;i<=n;++i)
g[now][i]=d[id].c[point[i]];
for(i=1;i<now;++i)
if(g[now][i])
elim(g[i],g[now],i);
for(i=now;i<=n;++i)
if(g[now][i])
{
swapl(now,i);
swap(point[now],point[i]);
break;
}
if(!g[now][now])
{
--now;
return 0;
}
return 1;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
LL i,j;
cin>>m>>n;
for(i=1;i<=m;++i)
for(j=1;j<=n;++j)
cin>>d[i].c[j];
for(i=1;i<=m;++i)
{
cin>>d[i].cost;
d[i].num=i;
}
sort(d+1,d+m+1,cmp);
for(i=1;i<=n;++i)
point[i]=i;
LL allcost=0,now=0;
for(i=1;i<=m;++i)
if(calc(now,i))
{
p[now]=d[i].num;
allcost+=d[i].cost;
}
if(now<n)
cout<<0<<endl;
else
{
cout<<allcost<<endl;
sort(p+1,p+n+1);
for(i=1;i<=n;++i)
cout<<p[i]<<endl;
}
return 1;
}




  评论这张
 
阅读(421)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018