博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
差分约束系统
阅读量:6085 次
发布时间:2019-06-20

本文共 11910 字,大约阅读时间需要 39 分钟。

变量之间的不等关系转成最短/长路求解。

若A - B <= x

则A <= B + x,此时有一条B->A边权为x的边。

不要忘了问题本身的约束条件。

求最小值->最长路

最大值->最短路

负环->无解

不连通->多解

例题:

HDU1384 Intervals 注意有多组数据。

1 #include 
2 #include
3 #include
4 5 const int N = 100010, INF = 0x3f3f3f3f; 6 7 struct Edge { 8 int nex, v, len; 9 Edge(int N = 0, int V = 0, int L = 0) {10 nex = N;11 v = V;12 len = L;13 }14 }edge[2000010]; int tp;15 16 std::queue
Q;17 int d[N], e[N], a[N], b[N], c[N];18 bool vis[N];19 20 inline void add(int x, int y, int z) {21 tp++;22 edge[tp] = Edge(e[x], y, z);23 e[x] = tp;24 return;25 }26 27 inline void spfa(int s) {28 memset(d, 0x3f, sizeof(d));29 vis[s] = 1;30 d[s] = 0;31 Q.push(s);32 while(!Q.empty()) {33 int x = Q.front();34 Q.pop();35 vis[x] = 0;36 for(int i = e[x]; i; i = edge[i].nex) {37 int y = edge[i].v;38 if(d[y] > d[x] + edge[i].len) {39 d[y] = d[x] + edge[i].len;40 if(!vis[y]) {41 vis[y] = 1;42 Q.push(y);43 }44 }45 }46 }47 return;48 }49 50 int main() {51 int n, lm = 0;52 while(scanf("%d", &n) != EOF) {53 memset(e, 0, sizeof(e));54 tp = 0;55 memset(vis, 0, sizeof(vis));56 for(int i = 1; i <= n; i++) {57 scanf("%d%d%d", &a[i], &b[i], &c[i]);58 a[i]++; b[i]++;59 lm = std::max(lm, b[i]);60 /// sum[b[i]] - sum[a[i] - 1] >= c[i]61 add(a[i], b[i] + 1, -c[i]);62 }63 for(int i = 1; i <= lm; i++) {64 add(i, i + 1, 0);65 add(i + 1, i, 1);66 }67 spfa(1);68 printf("%d\n", -d[lm + 1]);69 }70 return 0;71 }
AC代码

ZOJ2770 Burn the Linked Camp 一毛一样。多了一个判负环。

1 #include 
2 #include
3 #include
4 5 typedef long long LL; 6 const int N = 100010; 7 const LL INF = 0x3f3f3f3f3f3f3f3fll; 8 9 struct Edge {10 int nex, v;11 LL len;12 Edge(int N = 0, int V = 0, LL L = 0) {13 nex = N;14 v = V;15 len = L;16 }17 }edge[2000010]; int tp;18 19 std::queue
Q;20 int e[N], a[N], b[N], c[N], m, n, cnt[N];21 LL d[N];22 bool vis[N];23 24 inline void add(int x, int y, LL z) {25 tp++;26 edge[tp] = Edge(e[x], y, z);27 e[x] = tp;28 return;29 }30 31 inline int spfa(int s) {32 memset(d, 0x3f, sizeof(d));33 memset(cnt, 0, sizeof(cnt));34 memset(vis, 0, sizeof(vis));35 vis[s] = 1;36 d[s] = 0;37 cnt[s] = 1;38 Q.push(s);39 while(!Q.empty()) {40 int x = Q.front();41 Q.pop();42 vis[x] = 0;43 for(int i = e[x]; i; i = edge[i].nex) {44 int y = edge[i].v;45 if(d[y] > d[x] + edge[i].len) {46 d[y] = d[x] + edge[i].len;47 cnt[y] = cnt[x] + 1;48 if(cnt[y] > n + 1) {49 return -1;50 }51 if(!vis[y]) {52 vis[y] = 1;53 Q.push(y);54 }55 }56 }57 }58 return 0;59 }60 61 int main() {62 while(scanf("%d%d", &n, &m) != EOF) {63 memset(e, 0, sizeof(e));64 tp = 0;65 for(int i = 1; i <= n; i++) {66 scanf("%d", &c[i]);67 add(i + 1, i, c[i]);68 add(i, i + 1, 0);69 }70 for(int i = 1; i <= m; i++) {71 scanf("%d%d%d", &a[i], &b[i], &c[i]);72 add(a[i], b[i] + 1, -c[i]);73 }74 int t = spfa(1);75 if(t == -1) {76 printf("Bad Estimations\n");77 }78 else {79 printf("%d\n", -d[n + 1]);80 }81 }82 return 0;83 }
AC代码

HDU1531 King 注意可能不连通,而每个数也没有非负的限制,所以新建s向每个点连0边保证每个连通块都会被检查一遍。

1 #include 
2 #include
3 #include
4 5 typedef long long LL; 6 const int N = 100010; 7 const LL INF = 0x3f3f3f3f3f3f3f3fll; 8 9 struct Edge {10 int nex, v;11 LL len;12 Edge(int N = 0, int V = 0, LL L = 0) {13 nex = N;14 v = V;15 len = L;16 }17 }edge[1000010]; int tp;18 19 std::queue
Q;20 int e[N], a[N], b[N], c[N], m, n, cnt[N];21 LL d[N];22 bool vis[N];23 24 inline void add(int x, int y, LL z) {25 tp++;26 edge[tp] = Edge(e[x], y, z);27 e[x] = tp;28 return;29 }30 31 inline int spfa(int s) {32 memset(d, 0x3f, sizeof(d));33 memset(cnt, 0, sizeof(cnt));34 memset(vis, 0, sizeof(vis));35 vis[s] = 1;36 d[s] = 0;37 cnt[s] = 1;38 Q.push(s);39 while(!Q.empty()) {40 int x = Q.front();41 Q.pop();42 vis[x] = 0;43 for(int i = e[x]; i; i = edge[i].nex) {44 int y = edge[i].v;45 if(d[y] > d[x] + edge[i].len) {46 d[y] = d[x] + edge[i].len;47 cnt[y] = cnt[x] + 1;48 if(cnt[y] > n + 2) {49 return -1;50 }51 if(!vis[y]) {52 vis[y] = 1;53 Q.push(y);54 }55 }56 }57 }58 return 0;59 }60 61 char str[3];62 63 int main() {64 //printf("%d \n", (sizeof(edge) + sizeof(cnt) * 7) / 1048576);65 while(scanf("%d", &n), n) {66 scanf("%d", &m);67 memset(e, 0, sizeof(e));68 tp = 0;69 for(int i = 1; i <= m; i++) {70 scanf("%d%d%s%d", &a[i], &b[i], str, &c[i]);71 b[i] += a[i];72 if(str[0] == 'g') {73 c[i]++;74 add(b[i] + 1, a[i], -c[i]);75 }76 else {77 c[i]--;78 add(a[i], b[i] + 1, c[i]);79 }80 }81 for(int i = 1; i <= n + 1; i++) {82 add(n + 2, i, 0);83 }84 85 int t = spfa(n + 2);86 if(t != -1) {87 printf("lamentable kingdom\n");88 }89 else {90 printf("successful conspiracy\n");91 }92 }93 return 0;94 }
AC代码

HDU1534 Schedule Problem 之前的都是序列模型,这个直接就是点之间的关系,不需要序列上前缀和。

每个事件的开始时间就是d。

1 #include 
2 #include
3 #include
4 5 typedef long long LL; 6 const int N = 100010; 7 const LL INF = 0x3f3f3f3f3f3f3f3fll; 8 9 struct Edge { 10 int nex, v; 11 LL len; 12 Edge(int N = 0, int V = 0, LL L = 0) { 13 nex = N; 14 v = V; 15 len = L; 16 } 17 }edge[1000010]; int tp; 18 19 std::queue
Q; 20 int e[N], a[N], b[N], c[N], m, n, cnt[N], Time; 21 LL d[N]; 22 bool vis[N]; 23 24 inline void add(int x, int y, LL z) { 25 tp++; 26 edge[tp] = Edge(e[x], y, z); 27 e[x] = tp; 28 return; 29 } 30 31 inline int spfa(int s) { 32 memset(d, 0x3f, sizeof(d)); 33 memset(cnt, 0, sizeof(cnt)); 34 vis[s] = Time; 35 d[s] = 0; 36 cnt[s] = 1; 37 Q.push(s); 38 while(!Q.empty()) { 39 int x = Q.front(); 40 Q.pop(); 41 vis[x] = 0; 42 for(int i = e[x]; i; i = edge[i].nex) { 43 int y = edge[i].v; 44 if(d[y] > d[x] + edge[i].len) { 45 d[y] = d[x] + edge[i].len; 46 cnt[y] = cnt[x] + 1; 47 if(cnt[y] > n + 1) { 48 return -1; 49 } 50 if(vis[y] != Time) { 51 vis[y] = Time; 52 Q.push(y); 53 } 54 } 55 } 56 } 57 return 0; 58 } 59 60 char str[4]; 61 62 int main() { 63 //printf("%d \n", (sizeof(edge) + sizeof(cnt) * 7) / 1048576); 64 while(scanf("%d", &n), n) { 65 memset(e, 0, sizeof(e)); 66 Time++; 67 int x, y; 68 tp = 0; 69 for(int i = 1; i <= n; i++) { 70 scanf("%d", &a[i]); 71 } 72 while(scanf("%s", str)) { 73 if(str[0] == '#') break; 74 scanf("%d%d", &x, &y); 75 if(str[0] == 'F' && str[2] == 'S') { 76 add(y, x, a[x]); 77 } 78 else if(str[0] == 'F') { 79 add(y, x, -a[y] + a[x]); 80 } 81 else if(str[2] == 'F') { 82 add(y, x, -a[y]); 83 } 84 else { 85 add(y, x, 0); 86 } 87 } 88 for(int i = 1; i <= n; i++) { 89 add(n + 1, i, 0); 90 } 91 int t = spfa(n + 1); 92 printf("Case %d:\n", Time); 93 if(t == -1) { 94 printf("impossible\n"); 95 } 96 else { 97 for(int i = 1; i <= n; i++) { 98 printf("%d %d\n", i, -d[i]); 99 }100 }101 puts("");102 }103 return 0;104 }
AC代码

HDU1529 Cashier Employment 把每个时间的选用人数做前缀和。发现有7个不等式有三个变量,于是二分其中一个,也就是总共选了多少人。

1 #include 
2 3 typedef long long LL; 4 const int N = 110; 5 6 struct Edge { 7 int nex, v; 8 LL len; 9 Edge(int N = 0, int V = 0, LL L = 0) { 10 nex = N; 11 v = V; 12 len = L; 13 } 14 }edge[100010]; int tp; 15 16 int e[N], cnt[N], stk[N], top, n, m, a[N], vis[N], b[N]; 17 LL d[N]; 18 19 inline void add(int x, int y, LL z) { 20 tp++; 21 edge[tp] = Edge(e[x], y, z); 22 e[x] = tp; 23 return; 24 } 25 26 inline int spfa(int s) { 27 static int Time = 0; 28 Time++; 29 memset(d, 0x3f, sizeof(d)); 30 memset(cnt, 0, sizeof(cnt)); 31 stk[++top] = s; 32 vis[s] = Time; 33 cnt[s] = 1; 34 d[s] = 0; 35 while(top) { 36 int x = stk[top]; 37 top--; 38 vis[x] = 0; 39 for(int i = e[x]; i; i = edge[i].nex) { 40 int y = edge[i].v; 41 if(d[y] > d[x] + edge[i].len) { 42 d[y] = d[x] + edge[i].len; 43 cnt[y] = cnt[x] + 1; 44 if(cnt[y] > n + 1) { 45 return -1; 46 } 47 if(vis[y] != Time) { 48 vis[y] = Time; 49 stk[++top] = y; 50 } 51 } 52 } 53 } 54 return 0; 55 } 56 57 inline void clear() { 58 memset(b, 0, sizeof(b)); 59 tp = 0; 60 return; 61 } 62 63 inline bool check(int mid) { 64 memset(e, 0, sizeof(e)); 65 tp = 0; 66 for(int i = 1; i <= n; i++) { 67 add(i, i + 1, 0); 68 if(i < 8) { 69 add(i + 17, i + 1, -a[i] + mid); 70 } 71 else { 72 add(i - 7, i + 1, -a[i]); 73 } 74 add(i + 1, i, b[i]); 75 } 76 add(1, n + 1, -mid); 77 add(n + 1, 1, mid); 78 int t = spfa(1); 79 return t != -1; 80 } 81 82 inline void solve() { 83 n = 24; 84 for(int i = 1; i <= n; i++) { 85 scanf("%d", &a[i]); 86 } 87 scanf("%d", &m); 88 for(int i = 1; i <= m; i++) { 89 int x; 90 scanf("%d", &x); 91 b[x + 1]++; 92 } 93 /// calc 94 int l = 0, r = m + 1; 95 while(l < r) { 96 int mid = (l + r) >> 1; 97 if(check(mid)) { 98 r = mid; 99 }100 else {101 l = mid + 1;102 }103 }104 if(r == m + 1) {105 printf("No Solution\n");106 return;107 }108 printf("%d\n", r);109 return;110 }111 112 int main() {113 int T;114 scanf("%d", &T);115 while(T--) {116 solve();117 if(T) {118 clear();119 }120 }121 return 0;122 }
AC代码

 

转载于:https://www.cnblogs.com/huyufeifei/p/10448363.html

你可能感兴趣的文章
「翻译」逐步替换Sass
查看>>
H5实现全屏与F11全屏
查看>>
处理excel表的列
查看>>
C#数据采集类
查看>>
quicksort
查看>>
【BZOJ2019】nim
查看>>
LINUX内核调试过程
查看>>
【HDOJ】3553 Just a String
查看>>
Java 集合深入理解(7):ArrayList
查看>>
2019年春季学期第四周作业
查看>>
linux环境配置
查看>>
tomcat指定配置文件路径方法
查看>>
linux下查看各硬件型号
查看>>
epoll的lt和et模式的实验
查看>>
Flux OOM实例
查看>>
07-k8s-dns
查看>>
Android 中 ListView 分页加载数据
查看>>
oracle启动报错:ORA-00845: MEMORY_TARGET not supported on this system
查看>>
Go方法
查看>>
Dapper丶DapperExtention,以及AbpDapper之间的关系,
查看>>