`
暴风雪
  • 浏览: 387962 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[差分约束]hdoj 3666:THE MATRIX PROBLEM

阅读更多

 

大致题意:

    给出一个n*m的矩阵map,和两个数字L,U。求出是否存在这样的数列a[1~n],b[1~m]。使得对于每一个map[i][j]有map[i][j]*a[i]/b[j]大于等于L,小于等于U。

 

大致思路:

    用log运算把乘法转化为加法,求出不等式。然后做差分约束。另外注意一点,如果直接用每个点入队次数大于n来判定的话肯定会超时。

 

 

在牛人博客看到下面两种方法。

1:某个点入队次数大于sqrt(N)的时候

2:所有入队次数大于T * (N + M),其中T一般取2

这里用的是第一种。

 

 

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=2050;
const int mMax=1000050;
const int inf=1<<28;
struct{
    int u,v, next;
    double  w;
}edge[mMax];
int n, k, head[nMax];
double dis[nMax];
int que[nMax],m,sum[nMax];
bool vis[nMax];

void addedge(int a,int b,double w){
    edge[k].w = w;
    edge[k].u=a;
    edge[k].v=b;
    edge[k].next=head[a];
    head[a]=k;k++;
}

bool spfa(int s){      //始点,终点,总点数
    int i, hhead = 0, tail = 1;    //  长注释的地方就是从最小费用改到最大费用时需要变动的地方
    for(i = 0; i <= n; i ++){
        dis[i] = inf;////////////
        vis[i] = false;
    }
    dis[s] = 0;
    que[0] = s;
    vis[s] = true;
    while(tail != hhead){     //  循环队列实现。
        int u = que[hhead];
        vis[u] = false;
        for(int p = head[u]; p != 0; p = edge[p].next){
            int v = edge[p].v;     //  写成了edge[k].v,WA了一晚。
            if(dis[v] > dis[u] + edge[p].w){
                dis[v] = dis[u] + edge[p].w;
                if(!vis[v]){
                    vis[v] = true;
                    que[tail ++] = v;
                    if(tail == nMax) tail = 0;
                    if(++sum[v] >sqrt(n)) return false;     //  不包含初始的进栈。
                }
            }
        }
        hhead ++;
        if(hhead == nMax) hhead = 0;
    }
    return true;
}

int map[403][403];
int main(){
    int m,i,j,a,b,l,u,c,s;
    char str[20];
    while(scanf("%d%d%d%d",&a,&b,&l,&u)!=EOF){
        k=1;
        memset(head,0,sizeof(head));
        memset(sum,0,sizeof(sum));
        for(i=1;i<=a;i++){
            for(j=1;j<=b;j++){
                scanf("%d",&map[i][j]);
            }
        }
        n=a+b;
        s=n+2;      //s作为加入差分约束系统的“虚拟点”
        for(i=1;i<=n;i++){
            addedge(s,i,0);
        }
        for(i=1;i<=a;i++){
            for(j=1;j<=b;j++){
                addedge(i,j+a,log(map[i][j]*1.0)-log(l*1.0));
                addedge(j+a,i,log(u*1.0)-log(map[i][j]*1.0));
            }
        }
        if(spfa(s)){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}
0
0
分享到:
评论
1 楼 笔良文昌 2012-03-11  
Orz  访问量3000 
沾点仙气`~

相关推荐

    HDOJ题目分类 HDOJ题目分类

    【标题】:“HDOJ题目分类 HDOJ题目分类” HDOJ,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户...

    hdoj:杭电OJ题目源码记录 —— a source code of hdoj acm problem archive

    hdoj-problem-archive 杭电OJ题目源码记录 —— a source code of hdoj acm problem archive 简介 此项目为 的 题目以及代码仓库 src 中每一个文件夹代表一个题目 每个文件夹中都有 原题文档介绍.md 原题文档介绍.md...

    hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000

    【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...

    HDOJ离线版

    《HDOJ离线版:探索编程竞赛的智慧宝库》 HDOJ,全称为“杭州电子科技大学在线评测系统”(Hangzhou Dianzi University Online Judge),是中国早期的编程竞赛平台之一,深受广大编程爱好者和在校学生的喜爱。HDOJ...

    hdoj--acm题目,有注释

    "hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...

    HDOJ 80题 Java

    【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...

    HDOJ部分简单题(JAVA)

    HDOJ1000.java HDOJ1001.java HDOJ1089.java HDOJ1090.java HDOJ1091.java HDOJ1092.java HDOJ1093.java HDOJ1094.java HDOJ1095.java HDOJ1108.java HDOJ1406.java HDOJ2001.java HDOJ2002.java HDOJ2003.java HDOJ...

    HDOJ1002

    ACM ICPC HDOJ1002

    HDOJ1001

    ACM ICPC HDOJ1001

    hdoj1001标程

    hdoj1001标程

    hdoj2066最短路

    根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...

    hdoj1004 解题代码 答案

    hdoj1004,解题代码,答案代码,欢迎下载

    HDOJ 1008

    ACM ICPC HDOJ1008

    HDOJ1003

    ACM ICPC HDOJ1003

    hdoj 2013 多校训练4标程+解题报告

    【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...

    OJ.tar.gz_HDOJ _OJ源码_oj

    【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...

    ACM HDOJ 课件

    【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...

    hdoj杭电入门训练题

    The Hardest Problem Ever (HDOJ1048) **知识点:** - 动态规划。 - 状态转移方程。 **解题思路:** - 定义状态dp[i]表示到达第i个位置的方案数。 - 根据题目条件建立状态转移方程。 - 使用滚动数组优化空间复杂度...

    HDOJ.rar_HD_HDOJ

    【标题】"HDOJ.rar_HD_HDOJ" 是一个与HDU(杭州电子科技大学)在线判题系统HDOJ相关的压缩包文件,其中包含了大量编程题目的源代码。 【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵...

    HDOJ_1010 Tempter of the Bone

    【HDOJ_1010 诱惑者的骨头】是一道经典的图论问题,主要考察的是在特定时间约束下寻找图中的路径。题目要求我们判断在一个给定的环境中是否存在一条从入口到出口的可行路径。这涉及到图的遍历算法,如深度优先搜索...

Global site tag (gtag.js) - Google Analytics