HDU 3666 THE MATRIX PROBLEM (差分约束)
2024-08-29 09:00:50
题意:给定一个最大400*400的矩阵,每次操作可以将某一行或某一列乘上一个数,问能否通过这样的操作使得矩阵内的每个数都在[L,R]的区间内。
析:再把题意说明白一点就是是否存在ai,bj,使得l<=cij*(ai/bj)<=u (1<=i<=n,1<=j<=m)成立。
首先把cij先除到两边去,就变成了l'<=ai/bj<=u',由于差分约束要是的减,怎么变成减法呢?取对数呗,两边取对数得到log(l')<=log(ai)-log(bj)<=log(u')。
然后把ai, bj看成是两个点,那两个是权值,就可以差分约束了,但是。。这个题太坑了,会TLE,必须要判断好结束条件,就是访问次数超过sqrt(m+n),
就结束,如果不开根号,就会一直TLE。。。。有没有天理了。。。。
析:
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <stack>
using namespace std ; typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-10;
const int maxn = 800 + 5;
const int mod = 1e9 + 7;
const char *mark = "+-*";
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
int n, m;
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
int head[maxn], to[maxn*maxn/2], Next[maxn*maxn/2], cnt;
double w[maxn*maxn/2], l, u, d[maxn]; void addedge(int u, int v, double c){
to[cnt] = v;
w[cnt] = c;
Next[cnt] = head[u];
head[u] = cnt++;
}
int vis[maxn], num[maxn]; bool spfa(){
memset(vis, 0, sizeof(vis));
memset(num, 0, sizeof(num));
fill(d, d+n+m+1, inf);
queue<int> q;
vis[0] = 1; d[0] = 0; num[0] = 1;
q.push(0);
int limit = sqrt(m+n+0.5);//不开根号,想AC?都到没有。 while(!q.empty()){
int u = q.front(); q.pop();
vis[u] = 0;
for(int i = head[u]; i != -1; i = Next[i]){
int v = to[i];
double c = w[i];
if(!vis[v] && d[v] > d[u] + c){
if(++num[v] > limit) return false;
d[v] = d[u] + c;
q.push(v);
vis[v] = 1;
}
}
}
return true;
} int main(){
while(scanf("%d %d %lf %lf", &n, &m, &l, &u) == 4){
memset(head, -1, sizeof(head));
cnt = 0;
double ll = log(l);
double uu = log(u);
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
double x;
scanf("%lf", &x);
x = log(x);
addedge(i, j+n, x-ll);
addedge(j+n, i, uu-x);
}
}
if(spfa()) puts("YES");
else puts("NO");
}
return 0;
}
最新文章
- [unity]UGUI界面滑动,ScrollRect嵌套滑动
- Asp.net 后台添加CSS、JS、Meta标签
- mybatis 配置返回集合collection时只有一条记录
- python之元编程(元类实例)
- MyScript 手写识别数学公式、图形 自动计算
- cocos2d-x之猜数字游戏
- [转]tftp在put上传的时候显示File not found的解决办法
- 一些iOS笔试题目
- 《how to design programs》13章用list构造表
- IOS 技术层概览
- 基于linux c的mysql操作——幼儿园数据管理系统
- 阿里云centos 搭建SVN
- Excel 日期截取(函数)
- Install and Configure Apache Kafka on Ubuntu 16.04
- Delphi中常用字符串处理函数
- go标准库的学习-net/http
- 通过MTK迁移Mysql到EDB实战指南
- IAR中的 identifier ";FILE"; is undefined 问题
- oracle count 大表
- 转:QTCreater调试时提示ptrace不允许的操作(点击调试之后40秒钟gdb无回应)
热门文章
- CentOS5.5 正式开始安装 Oracle 11g r2(图形界面安装)
- ios程序开发杂记
- HDU 4635 Strongly connected (强连通分量)
- 使用D3D渲染YUV视频数据
- webview javascript 注入方法
- 新闻类App使用的组件
- 【转】Select模型原理
- Vijos 1132 求二叉树的先序序列
- hdu 3172 Virtual Friends(并查集)University of Waterloo Local Contest 2008.09
- 完全参照系统自带的DatePickerDialog、TimePickerDialog的源代码仿写的DateTimePickerDialog