Burn the Linked Camp
It is well known that, in the period of The Three Empires, Liu Bei, the emperor of the Shu Empire, was defeated by Lu Xun, a general of the Wu Empire. The defeat was due to Liu Bei's wrong decision that he divided his large troops into a number of camps, each of which had a group of armies, and located them in a line. This was the so-called "Linked Camps".
Let's go back to that time. Lu Xun had sent many scouts to obtain the information about his enemy. From his scouts, he knew that Liu Bei had divided his troops into n camps, all of which located in a line, labeled by 1..n from left to right. The ith camp had a maximum capacity of Ci soldiers. Furthermore, by observing the activities Liu Bei's troops had been doing those days, Lu Xun could estimate the least total number of soldiers that were lived in from the ith to the jth camp. Finally, Lu Xun must estimate at least how many soldiers did Liu Bei had, so that he could decide how many troops he should send to burn Liu Bei's Linked Camps.
Input:
There are multiple test cases! On the first line of each test case, there are two integers n (0<n<=1,000) and m (0<=m<=10,000). On the second line, there are n integers C1��Cn. Then m lines follow, each line has three integers i, j, k (0<i<=j<=n, 0<=k<2^31), meaning that the total number of soldiers from the ith camp to the jth camp is at least k.
Output:
For each test case, output one integer in a single line: the least number of all soldiers in Liu Bei's army from Lu Xun's observation. However, Lu Xun's estimations given in the input data may be very unprecise. If his estimations cannot be true, output "Bad Estimations" in a single line instead.
Sample Input:
3 2
1000 2000 1000
1 2 1100
2 3 1300
3 1
100 200 300
2 3 600
Sample Output:
1300
Bad Estimations
题目类型：差分约束系统
算法分析：设每个军营人数为Ai，前i个军营总人数为Si。则由0 <= Ai <= Ci可以列出两个差分方程组。然后由Ki <= Aj - Ai-1 <= Dj - Di-1可以再列出两个方程组。最后由方程组构建有向图。本题最后要求的是Sn - S0的最小值，即Sn - S0 >= val。可以转换成求解S0 - Sn <= -val，也就是从顶点n到0的最短路相反数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
/************************************************* Author :supermaker Created Time :2016/3/18 19:46:11 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1000 + 66; struct Node { int v, w, nxt; }; int head[maxn], edgelen; Node edge[maxn*maxn]; void Init () { memset (head, -1, sizeof (head)); memset (edge, -1, sizeof (edge)); edgelen = 0; } void AddEdge (int u, int v, int w) { edge[edgelen].v = v, edge[edgelen].w = w; edge[edgelen].nxt = head[u]; head[u] = edgelen++; } int dis[maxn], inq[maxn], cnt[maxn], n, m; bool is_valid; void spfa (int s) { for (int i = 0; i <= n; i++) { dis[i] = INF; inq[i] = cnt[i] = 0; } dis[s] = 0; is_valid = true; queue <int> qu; qu.push (s); inq[s]++; cnt[s]++; while (!qu.empty ()) { int tt = qu.front (); qu.pop (); inq[tt]--; if (cnt[tt] > n + 1) { is_valid = false; return ; } int pa = head[tt]; while (pa != -1) { int pb = edge[pa].v; if (dis[tt] < INF && dis[pb] > dis[tt] + edge[pa].w) { dis[pb] = dis[tt] + edge[pa].w; if (!inq[pb]) { qu.push (pb); inq[pb]++; cnt[pb]++; } } pa = edge[pa].nxt; } } } int C[maxn], SC[maxn]; int main() { //CFF; //CPPFF; while (scanf ("%d%d", &n, &m) != EOF) { Init (); memset (SC, 0, sizeof (SC)); for (int i = 1; i <= n; i++) { scanf ("%d", &C[i]); AddEdge (i, i - 1, 0); AddEdge (i - 1, i, C[i]); SC[i] = SC[i-1] + C[i]; } for (int i = 1; i <= m; i++) { int u, v, w; scanf ("%d%d%d", &u, &v, &w); AddEdge (v, u - 1, -w); AddEdge (u - 1, v, SC[v] - SC[u-1]); } spfa (n); if (is_valid) printf ("%d\n", dis[n] - dis[0]); else puts ("Bad Estimations"); } return 0; } |
- « 上一篇：poj1392
- poj1201：下一篇 »