POJ1201Intervals(差分约束系统)-白红宇

POJ1201Intervals(差分约束系统)

阅读量：6300 次

发布时间：2019-06-22

本文共 2100 字，大约阅读时间需要 7 分钟。

昨天看了下差分约数系统的含义，其实就是如果有n个变量在m个形如aj-ai>=bk条件下，求解的此不等式的方法。

而这种不等式的解法其实就是转化为图论的最小路的算法求解的。我们将上面的不等式边形后得到aj>=ai+bk正好就可以看做是从ai到aj权值是bk的一条路径最短的边。这样一来，只要依照题目的条件写出一系列这样的不等式，也就是相当于按照题意增加了一些合法的边，也就完全转化为了最短路的算法。

再看这道题，题目说[ai, bi]区间内和点集Z至少有ci个共同元素，那也就是说如果我用Si表示区间[0,i]区间内至少有多少个元素的话，那么Sbi - Sai >= ci,这样我们就构造出来了一系列边，权值为ci，但是这远远不够，因为有很多点依然没有相连接起来（也就是从起点可能根本就还没有到终点的路线）,此时，我们再看看Si的定义，也不难写出0<=Si - Si-1<=1的限制条件，虽然看上去是没有什么意义的条件，但是如果你也把它构造出一系列的边的话，这样从起点到终点的最短路也就顺理成章的出现了。

我们将上面的限制条件写为同意的形式：

Sbi - Sai >= ci

Si - Si-1 >= 0

Si-1 - Si >= -1

这样一来就构造出了三种权值的边，而最短路自然也就没问题了。

但要注意的是，由于查分约束系统里常常会有负权边，所以为了避免负权回路，往往用Bellman-Ford或是SPFA求解（存在负权回路则最短路不存在）。

1 #include  2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 using namespace std;15 #define eps 1e-1516 #define MAXN 5000517 #define INF 100000000718 #define MAX(a,b) (a > b ? a : b)19 #define MIN(a,b) (a < b ? a : b)20 #define mem(a) memset(a,0,sizeof(a))21 22 struct EDGE//使用邻接表存边23 {24 int v;25 int w;26 int next;27 }edge[3*MAXN];28 int head[MAXN], d[MAXN], vis[MAXN],N, n, Max,Min;29 30 void AddEdge(int u,int v,int w)//添加新边31 {32 edge[N].v = v;33 edge[N].w = w;34 edge[N].next = head[u];35 head[u] = N++;36 }37 38 void SPFA()//此题数据较大，用Bellman-ford恐怕过不了39 {40 for(int i=Min;i<=Max;i++) d[i] = -INF;41 d[Min] = 0;42 queue
                  
                   q;43 q.push(Min);44 while(!q.empty())45 {46 int x = q.front(); q.pop();47 vis[x] = 0;48 for(int e=head[x];e != -1;e=edge[e].next)if(d[edge[e].v] < d[x] + edge[e].w)49 {50 d[edge[e].v] = d[x] +edge[e].w;51 if(!vis[edge[e].v])52 {53 q.push(edge[e].v);54 vis[edge[e].v] = 1;55 }56 }57 }//由于题目说一定有解，我就略去了判断是否存在负权回路58 }59 60 int main()61 {62 while(~scanf("%d", &n))63 {64 int u,v,w; N = 0;65 memset(head,-1,sizeof(head));66 mem(vis); mem(edge);67 Min = INF; Max = -INF;68 for(int i=0;i
                   
                    < Max; i++)//添加新边76 {77 AddEdge(i,i+1,0);78 AddEdge(i+1,i,-1);79 }80 SPFA();81 printf("%d\n", d[Max]);82 }83 return 0;84 }

转载于:https://www.cnblogs.com/gj-Acit/p/3261721.html

你可能感兴趣的文章