本文共 4357 字，大约阅读时间需要 14 分钟。
线段树+spfa求最长路。
1 /* 3016 */ 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 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set 25 #define stpii set > 26 #define mpii map 27 #define vi vector 28 #define pii pair 29 #define vpii vector > 30 #define rep(i, a, n) for (int i=a;i =a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 42 typedef struct { 43 int v, w, nxt; 44 } edge_t; 45 46 typedef struct node_t { 47 int h, xl, xr, w; 48 49 node_t() {} 50 51 friend bool operator< (const node_t& a, const node_t& b) { 52 return a.h < b.h; 53 } 54 55 } node_t; 56 57 const int BASE = 1001; 58 const int maxn = 1e5+5; 59 const int maxv = 1e5+5; 60 const int maxe = 5e5+5; 61 node_t nd[maxv]; 62 bool mark[maxn<<2]; 63 int ID[maxn<<2]; 64 int X[maxn]; 65 edge_t E[maxe]; 66 int head[maxv]; 67 int dis[maxv]; 68 bool visit[maxv]; 69 int m; 70 71 void init() { 72 memset(head, -1, sizeof(head)); 73 m = 0; 74 } 75 76 void addEdge(int u, int v, int w) { 77 E[m].v = v; 78 E[m].w = w; 79 E[m].nxt = head[u]; 80 head[u] = m++; 81 } 82 83 inline void PushDown(int rt) { 84 if (mark[rt]) { 85 ID[rt<<1] = ID[rt<<1|1] = ID[rt]; 86 mark[rt<<1] = mark[rt<<1|1] = true; 87 mark[rt] = false; 88 } 89 } 90 91 void Build(int l, int r, int rt) { 92 mark[rt] = true; 93 ID[rt] = 0; 94 if (l == r) 95 return ; 96 97 int mid = (l + r) >> 1; 98 Build(lson); 99 Build(rson);100 }101 102 void Update(int L, int R, int id, int l, int r, int rt) {103 if (L<=l && R>=r) {104 ID[rt] = id;105 mark[rt] = true;106 return ;107 }108 109 PushDown(rt);110 int mid = (l + r) >> 1;111 112 if (L > mid) {113 Update(L, R, id, rson);114 } else if (R <= mid) {115 Update(L, R, id, lson);116 } else {117 Update(L, R, id, lson);118 Update(L, R, id, rson);119 }120 }121 122 int Query(int x, int l, int r, int rt) {123 if (l == r)124 return ID[rt];125 126 PushDown(rt);127 int mid = (l + r) >> 1;128 129 if (x <= mid)130 return Query(x, lson);131 else132 return Query(x, rson);133 }134 135 int spfa(int s, int t) {136 queue Q;137 int u, v, k;138 139 memset(dis, 0, sizeof(dis));140 memset(visit, false, sizeof(visit));141 dis[s] = 100;142 visit[s] = true;143 Q.push(s);144 145 while (!Q.empty()) {146 u = Q.front();147 Q.pop();148 visit[u] = false;149 for (k=head[u]; k!=-1; k=E[k].nxt) {150 v = E[k].v;151 if (dis[u]+E[k].w > dis[v]) {152 dis[v] = dis[u] + E[k].w;153 if (!visit[v]) {154 visit[v] = true;155 Q.push(v);156 }157 }158 }159 }160 161 int ret = (dis[t]==0) ? -1 : dis[t];162 return ret;163 }164 165 int main() {166 ios::sync_with_stdio(false);167 #ifndef ONLINE_JUDGE168 freopen("data.in", "r", stdin);169 freopen("data.out", "w", stdout);170 #endif171 172 int n;173 int lid;174 int rid;175 int ans;176 int src, des;177 178 while (scanf("%d", &n) != EOF) {179 memset(visit, false, sizeof(visit));180 rep(i, 1, n+1) {181 scanf("%d %d %d %d", &nd[i].h, &nd[i].xl, &nd[i].xr, &nd[i].w);182 visit[nd[i].xl] = visit[nd[i].xr] = true;183 }184 sort(nd+1, nd+1+n);185 if (nd[n].w <= -100) {186 puts("-1");187 continue;188 }189 int nx = 0;190 rep(i, 0, maxn) {191 if (visit[i])192 X[i] = ++nx;193 }194 src = 0;195 des = n+1;196 197 init();198 Build(1, nx, 1);199 Update(X[nd[1].xl], X[nd[1].xr], 1, 1, nx, 1);200 addEdge(1, des, 0);201 rep(i, 2, n+1) {202 lid = Query(X[nd[i].xl], 1, nx, 1);203 if (lid)204 addEdge(i, lid, nd[lid].w);205 else206 addEdge(i, des, 0);207 rid = Query(X[nd[i].xr], 1, nx, 1);208 if (rid) {209 if (lid != rid)210 addEdge(i, rid, nd[rid].w);211 } else {212 addEdge(i, des, 0);213 }214 Update(X[nd[i].xl], X[nd[i].xr], i, 1, nx, 1);215 }216 addEdge(src, n, nd[n].w);217 218 ans = spfa(src, des);219 printf("%d\n", ans);220 }221 222 #ifndef ONLINE_JUDGE223 printf("time = %d.\n", (int)clock());224 #endif225 226 return 0;227 }
转载于:https://www.cnblogs.com/bombe1013/p/5069600.html