首页 > 编程学习 > HDU 3666 THE MATRIX PROBLEM (差分约束判负环)

HDU 3666 THE MATRIX PROBLEM (差分约束判负环)

发布时间:2022/9/14 11:45:51

分类: ACM_HDU ACM_图论 226人阅读 评论(0) 收藏 举报
差分约束

题意:

给你一个N*M的矩阵C,问是否存在一个长度为N的数列a和长度为M的数列b使得所有C(i,j)*a(i)/b(j)在L , U范围内。


解题思路:

有两个式子 C(i,j)*a(i)/b(j) >= L   ,  C(i,j)*a(i)/b(j) <= U ,两边均取对数得到 log(i) - log(j) <= log( U/C(i , j) )  和 log(j) - log(i)  <= log( C(i,j) / L) ,很显然的差分约束。。可惜用普通的队列版SPFA是会TLE的!网上说只需要入队sqrt(n)次就可以判断有负环了,不过没有具体的证明解释呀!所以正解应该是DFS版的也就是用栈的SPFA,因为要找负环,DFS找到一个负环后接下来相当于一直会绕着这个负环走个n+1次就跳出了,比BFS版判负环高效的多!


[cpp] view plaincopy
  1. /* ********************************************** 
  2. Author      : JayYe 
  3. Created Time: 2013-10-23 16:18:20 
  4. File Name   : JayYe.cpp 
  5. *********************************************** */  
  6.   
  7. #include <stdio.h>  
  8. #include <math.h>  
  9. #include <string.h>  
  10. #include <algorithm>  
  11. using namespace std;  
  12.   
  13. const int maxn = 800 + 5;  
  14. const int INF = 2000000000;  
  15.   
  16. struct Edge{  
  17.     int to, next;  
  18.     double w;  
  19. }edge[maxn*maxn*2];  
  20.   
  21. int head[maxn], T[maxn], E, q[maxn*maxn];  
  22. bool vis[maxn];  
  23.   
  24. void init(int n) {  
  25.     for(int i = 0;i <= n; i++)  
  26.         head[i] = -1;  
  27.     E = 0;  
  28. }  
  29.   
  30. void newedge(int u, int to, double w) {  
  31.     edge[E].to = to;  
  32.     edge[E].w = w;  
  33.     edge[E].next = head[u];  
  34.     head[u] = E++;  
  35. }  
  36. double dis[maxn];  
  37.   
  38. bool SPFA(int n) {  
  39.     for(int i = 0;i <= n; i++) {  
  40.         dis[i] = INF; vis[i] = T[i] = 0;  
  41.     }  
  42.     T[0] = 1;  
  43.     dis[0] = 0;  
  44.     vis[0] = 1;  
  45.     int st = 0, ed = 0;  
  46.     q[++ed] = 0;  
  47.     while(ed) {  
  48.         int u = q[ed--];  
  49.         //if(st > n*n)    return false;  
  50.         vis[u] = 0;  
  51.         for(int i = head[u];i != -1;i = edge[i].next) {  
  52.             int to = edge[i].to;  
  53.             double w = edge[i].w;  
  54.             if(dis[to] > dis[u] + w) {  
  55.                 dis[to] = dis[u] + w;  
  56.                 if(!vis[to]) {  
  57.                     vis[to] = 1;  
  58.                     T[to]++;  
  59.                     if(T[to] > n + 1 ) return true;  
  60.                     q[++ed] = to;  
  61.                 }  
  62.             }  
  63.         }  
  64.     }  
  65.     return false;  
  66. }  
  67.   
  68. int main() {  
  69.     int n, m, L, U, c;  
  70.     while(scanf("%d%d%d%d", &n, &m, &L, &U) != -1) {  
  71.         init(n+m);  
  72.         for(int i = 1;i <= n; i++) {  
  73.             for(int j = 1;j <= m; j++) {  
  74.                 scanf("%d", &c);  
  75.                 newedge(j + n, i, log((double)U) - log((double)c));  
  76.                 newedge(i, j + n, log((double)c) - log((double)L));  
  77.             }  
  78.         }  
  79.         for(int i = 1;i <= n+m; i++)    newedge(0, i, 0);  
  80.         if(!SPFA(n + m))  puts("YES");  
  81.         else    puts("NO");  
  82.     }  
  83.     return 0;  
  84. }  

本文链接:https://www.ngui.cc/el/1380839.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000