bzoj 4004 向量拟阵
2024-08-28 20:55:27
题解RT.
eps = 1e-10 WrongAnswer
eps = 1e-5 Accepted
/**************************************************************
Problem: 4004
User: idy002
Language: C++
Result: Accepted
Time:516 ms
Memory:2844 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <algorithm>
#define eps 1e-5
#define N 510
using namespace std; int n, m;
double aa[N][N];
int cost[N];
int vid[N];
int kid[N]; int sg( double x ) {
return (x>-eps)-(x<eps);
}
bool cmp( int a, int b ) { return cost[a]<cost[b]; }
bool join( int id ) {
for( int i=; i<=m; i++ ) {
if( sg(aa[id][i])== ) continue;
if( kid[i]== ) {
kid[i]=id;
return true;
}
int uid = kid[i];
double k = aa[id][i]/aa[uid][i];
for( int j=i; j<=m; j++ )
aa[id][j] -= k*aa[uid][j];
}
return false;
}
int main() {
scanf( "%d%d", &n, &m );
for( int i=; i<=n; i++ )
for( int j=; j<=m; j++ )
scanf( "%lf", &aa[i][j] );
for( int i=; i<=n; i++ )
scanf( "%d", cost+i );
for( int i=; i<=n; i++ )
vid[i] = i;
sort( vid+, vid++n, cmp );
memset( kid, , sizeof(kid) );
int cnt=, ans=;
for( int i=; i<=n; i++ ) {
int id = vid[i];
if( join(id) ) {
cnt++;
ans+=cost[id];
}
}
printf( "%d %d\n", cnt, ans );
}
最新文章
- 1、ASP.NET MVC入门到精通——新语法
- 共享onload事件
- 让Team Foundation Server/TFS自动记住用户名密码解决方案
- ThreadPool线程池 小结
- Elasticsearch + logstash中文指南
- Ubuntu C++环境支持
- OC - 8.Quartz2D核心要点
- Angularjs总结(三)摸态框的使用
- Erlang安装简介
- Selenium+Python之163邮件发送
- python 对象和json互相转换
- Oracle使用游标查询指定数据表的所有字段名称组合而成的字符串
- Python_正则表达式一
- TPshop之邮箱注册配置教程--附加常见问题集合
- nsqadmin
- 利用BLKTRACE分析IO性能
- 模组 前后端分离CURD 组件
- [WC2006]水管局长
- python入门(十):模块、包
- itext实现pdf自动定位合同签订
热门文章
- 20155320 2016-2017-2《Java程序设计》第八周学习总结
- 在pycharm和tensorflow环境下运行nmt
- BGM时长
- 联通-长春处,FDD和TDD宏站,数据业务接入时延期望值默认值应为80ms
- android的USB MTP &;&; USB CDC/USBnet(ECM, NCM, ACM) &;&; USB gardget
- centos memcached
- 二、vue中组件的使用
- ida自动编译配置
- Java流程控制练习--万年历
- K-Means和K Nearest Neighbor