首页 > 代码库 > ZOJ 3668 Launching the Spacecraft (差分约束系统，最短路)
ZOJ 3668 Launching the Spacecraft (差分约束系统，最短路)
题目：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3668
题意：
给一个初始值为0的长度为n的区间，给m个约束l,r,a,b，表示从l到r的区间和>=a且<=b，且每个数的范围为-10000~10000，问这个区间的每个数是多少，要求数尽可能大，且序列字典序最大。
方法：
差分约束系统，以前缀和表示一个节点a[i]
建图：根据下面约束条件建图
a[i]-a[i-1]<=10000
a[i-1]-a[i]<=10000
对于每个条件(l,r,a,b)
a[r]-a[l-1]<=-a
a[l-1]-a[r]<=b
使用最短路尽可能求最大值
(最长路求最小值，最短路求最大值)
1 void add(int l, int r, int a, int b) 2 { 3 addse(l - 1, r, b); 4 addse(r, l - 1, -a); 5 } 6 void input() 7 { 8 for (int i = 1; i <= n; i++) 9 {10 addse(i, i - 1, 10000);11 addse(i - 1, i, 10000);12 }13 for (int i = 0; i < m; i++)14 {15 int l, r, a, b;16 scanf("%d%d%d%d", &l, &r, &a, &b);17 add(l, r, a, b);18 }19 }
代码：
1 /******************************************** 2 *ACM Solutions 3 * 4 *@Title: ZOJ 3668 Launching the Spacecraft 5 *@Version: 1.0 6 *@Time: 2014-08-26 7 *@Solution: http://www.cnblogs.com/xysmlx/p/xxxxxxx.html 8 * 9 *@Author: xysmlx(Lingxiao Ma) 10 *@Blog: http://www.cnblogs.com/xysmlx 11 *@EMail: xysmlx@163.com 12 * 13 *Copyright (C) 2011-2015 xysmlx(Lingxiao Ma) 14 ********************************************/ 15 // #pragma comment(linker, "/STACK:102400000,102400000") 16 #include <cstdio> 17 #include <iostream> 18 #include <cstring> 19 #include <string> 20 #include <cmath> 21 #include <set> 22 #include <list> 23 #include <map> 24 #include <iterator> 25 #include <cstdlib> 26 #include <vector> 27 #include <queue> 28 #include <stack> 29 #include <algorithm> 30 #include <functional> 31 using namespace std; 32 typedef long long LL; 33 #define pb push_back 34 #define ROUND(x) round(x) 35 #define FLOOR(x) floor(x) 36 #define CEIL(x) ceil(x) 37 const int maxn = 1010; 38 const int maxm = 2000010; 39 const int inf = 0x3f3f3f3f; 40 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL; 41 const double INF = 1e30; 42 const double eps = 1e-6; 43 const int P[4] = {0, 0, -1, 1}; 44 const int Q[4] = {1, -1, 0, 0}; 45 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1}; 46 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1}; 47 struct Edge 48 { 49 int u, v, w; 50 int next; 51 } edge[maxm]; 52 int head[maxn], en; 53 void addse(int u, int v, int w) 54 { 55 edge[en].u = u; 56 edge[en].v = v; 57 edge[en].w = w; 58 edge[en].next = head[u]; 59 head[u] = en++; 60 } 61 62 int n, m; 63 int d[maxn]; 64 int pre[maxn];//用于解析路径 65 /*DFS找负环 66 bool cir[maxn]; 67 void dfs(int u) 68 { 69 cir[u]=true; 70 for(int i=head[u]; i!=-1; i=edge[i].next) 71 if(!cir[edge[i].v]) dfs(edge[i].v); 72 } 73 */ 74 bool spfa(int s) 75 { 76 int cnt[maxn]; 77 int mark[maxn]; 78 queue<int> Q; 79 for (int i = 0; i <= n; ++i) d[i] = inf; 80 for (int i = 0; i <= n; ++i) pre[i] = i; //用于解析路径 81 memset(mark, 0, sizeof(mark)); 82 memset(cnt, 0, sizeof(cnt)); 83 d[s] = 0; 84 Q.push(s); 85 mark[s] = 1; 86 cnt[s]++; 87 while (Q.size()) 88 { 89 int u = Q.front(); 90 Q.pop(); 91 mark[u] = 0; 92 for (int i = head[u]; i != -1; i = edge[i].next) 93 { 94 int v = edge[i].v; 95 int w = edge[i].w; 96 if (d[u] + w < d[v]) 97 { 98 pre[v] = u; // 用于解析路径 99 d[v] = d[u] + w;100 if (mark[v] == 0)101 {102 mark[v] = 1;103 Q.push(v);104 if (++cnt[v] > n + 1) return false; //有负环，可以用DFS找105 }106 }107 }108 }109 return true;110 }111 int kase;112 void init()113 {114 kase++;115 memset(head, -1, sizeof(head));116 en = 0;117 }118 void add(int l, int r, int a, int b)119 {120 addse(l - 1, r, b);121 addse(r, l - 1, -a);122 }123 void input()124 {125 for (int i = 1; i <= n; i++)126 {127 addse(i, i - 1, 10000);128 addse(i - 1, i, 10000);129 }130 for (int i = 0; i < m; i++)131 {132 int l, r, a, b;133 scanf("%d%d%d%d", &l, &r, &a, &b);134 add(l, r, a, b);135 }136 }137 void debug()138 {139 //140 }141 void solve()142 {143 if (spfa(0))144 {145 for (int i = 1; i <= n; i++)146 {147 if (i < n) printf("%d ", d[i] - d[i - 1]);148 else printf("%d\n", d[i] - d[i - 1]);149 }150 }151 else puts("The spacecraft is broken!");152 }153 void output()154 {155 //156 }157 int main()158 {159 // int size = 256 << 20; // 256MB160 // char *p = (char *)malloc(size) + size;161 // __asm__("movl %0, %%esp\n" :: "r"(p));162 163 // std::ios_base::sync_with_stdio(false);164 #ifdef xysmlx165 freopen("in.cpp", "r", stdin);166 #endif167 168 kase = 0;169 while (~scanf("%d%d", &n, &m))170 {171 init();172 input();173 solve();174 output();175 }176 return 0;177 }
ZOJ 3668 Launching the Spacecraft (差分约束系统，最短路)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。