浅谈差分约束系统——图论不等式的变形
2018-06-17 23:22:16来源:未知 阅读 ()
浅谈差分约束系统——图论不等式的变形
----yangyaojia
版权声明:本篇随笔版权归作者YJSheep(www.cnblogs.com/yangyaojia)所有,转载请保留原地址!
一.定义
如若一个系统由n个变量和m个不等式组成,并且这m个不等式对应的系数矩阵中每一行有且仅有一个1和-1,其它的都为0,这样的系统称为差分约束( difference constraints )系统。
二.分析
简单来说就是给你n个变量,给m个形如x[i]-x[j]≥k①或x[i]-x[j]≤k②。求两个变量差的最大与最小值。我们可以对不等式稍稍变形,将①变为k+aj≤ai,②变为ai+(-k)≤aj。不难发现,这和我们的最短路问题中的不等式dis[i]+w[i,j]≤dis[j]极为相似。
最大值
那么,如果题目要求我们求出某两点之间的最大距离,我们可以这样:
- 对于x[i] - x[j]≤a[k],我们可以建一条由j到i的有向边,权值为k
- 对于x[i] - x[j]≥a[k],我们可以建一条由i到j的有向边,权值为-k
并进行如下判断。
- 如果存在最短路径可以到达这两点,答案就是最短路的长度。
- 如果不存在路径可以到达,那么两点间的距离可以是无限大。
- 如果图中存在负环,那么就无解。
最小值
如果题目要求求出两点间的最小距离,我们就建立形如x[i]-x[j]≥k,建立i到j,权值为k的路,求的最长路径。判断也跟上面一样,不过是判有没有正环。
下面来附上一道典型例题 POJ3169
#include<queue> #include <algorithm> #include<cstdio> #include<cstring> #include<cmath> #define Pair pair<int,int> #define MAXN 1000+1 #define MAX 99999999 #define MAXM 40000+1 using namespace std; int n,m1,m2,num,nnum,head[MAXN],s,o,pre[MAXN],v[MAXN],K; int dis[MAXN],t[MAXN],ans=MAX; struct Edge{ int next,to,exi,from; int dis,cost; }edge[MAXM]; int read() { int in=0;char c; c=getchar(); for(;c>'9'||c<'0';c=getchar()); for(;c<='9'&&c>='0';c=getchar()) in=in*10+c-'0'; return in; } void add(int from,int to,int dis) { edge[++num].next=head[from]; edge[num].to=to; edge[num].dis=dis; edge[num].from=from; head[from]=num; } int spfa() { for(int i=1;i<=n;i++) dis[i]=99999999; queue<int> q; dis[s]=0;t[s]++; q.push(s); while(q.size()>0) { int k=q.front();q.pop(); v[k]=0; for(int i=head[k];i;i=edge[i].next) { if(dis[edge[i].to]>dis[k]+edge[i].dis) { dis[edge[i].to]=dis[k]+edge[i].dis; t[edge[i].to]++; if(t[edge[i].to]>n) return 1; if(!v[edge[i].to]) v[edge[i].to]=1,q.push(edge[i].to); } } } return 0; } int main() { scanf("%d%d%d",&n,&m1,&m2); int a,b,c; for(int i=1;i<=m1;i++) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); } for(int i=1;i<=m2;i++) { scanf("%d%d%d",&a,&b,&c); add(b,a,-c); }s=1; if(spfa()) { printf("-1\n"); return 0; } if(dis[n]==99999999) printf("-2\n"); else printf("%d\n",dis[n]); return 0; }
题目大意就是个一些约束条件求最大值,只要按着方法去建模,判断,就可以出解。
三.其他
差分约束还分线性约束,区间约束与未知条件的约束。但本质上就是一样的,都是建立最短路模型来求解。关于未知条件的约束的题目,也是枚举k的大小求解。在这里也不再多说,毕竟是浅谈差分约束。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 浅谈LCA 2019-12-25
- P2352 队爷的新书(差分) 2019-10-28
- P3028 汽水机(差分) 2019-10-28
- 浅谈高精度算法(加减乘除) 2019-08-16
- C++_调用约束 2019-03-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash