﻿ [BZOJ 3218]a + b Problem

### [BZOJ 3218]a + b Problem

这种题是不是非要来卡空间不然不痛快是吗？！！！！！

1 #include <cstdio>
2 #include <cstring>
3 const int sizeOfSegment=500005;
4 const int sizeOfEdge=1000001;
5 const int sizeOfPoint=500005;
6 const int sizeOfCell=5005;
7 const int inf=1000000000;
8
9 inline int min(int, int);
10 inline int getint();
11 inline void putint(int);
12
13 int S, T;
14 int V;
15 int n;
16 int a[sizeOfCell], b[sizeOfCell], w[sizeOfCell], l[sizeOfCell], r[sizeOfCell], p[sizeOfCell];
17
18 struct edge {int point, flow; edge * next, * pair;};
19 edge memory_edge[sizeOfEdge], * port_edge=memory_edge;
20 edge * e[sizeOfPoint];
21 inline edge * newedge(int, int, edge * );
22 inline void link(int, int, int);
23 int h[sizeOfPoint], gap[sizeOfPoint];
24 inline bool bfs();
25 inline int isap();
26
27 struct seg {int p; seg * l, * r;};
28 seg memory_seg[sizeOfSegment], * port_seg=memory_seg;
29 seg * t;
30 inline seg * newseg(seg * =NULL);
31 seg * insert(seg * , int, int, int, int);
32 void query(seg * , int, int, int, int, int);
33
34 int main()
35 {
36     int ans=0;
37
38     n=getint();
39     S=0; T=n+1; V=n+1;
40     for (int i=1;i<=n;i++)
41     {
42         a[i]=getint(), b[i]=getint(), w[i]=getint(), l[i]=getint(), r[i]=getint(), p[i]=getint();
43         ans+=b[i]+w[i];
44         link(S, i, b[i]); link(i, T, w[i]);
45         link(i, ++V, p[i]);
46         query(t, 0, inf, l[i], r[i], V);
47         t=insert(t, 0, inf, a[i], i);
48     }
49
50     ans-=isap();
51     putint(ans);
52
53     return 0;
54 }
55 inline int min(int x, int y)
56 {
57     return x<y?x:y;
58 }
59 inline int getint()
60 {
61     register int num=0;
62     register char ch;
63     do ch=getchar(); while (ch<'0' || ch>'9');
64     do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
65     return num;
66 }
67 inline void putint(int num)
68 {
69     char stack[11];
70     register int top=0;
71     if (num==0) stack[top=1]='0';
72     for ( ;num;num/=10) stack[++top]=num%10+'0';
73     for ( ;top;top--) putchar(stack[top]);
74     putchar('
');
75 }
76 inline edge * newedge(int point, int flow, edge * next)
77 {
78     edge * ret=port_edge++;
79     ret->point=point; ret->flow=flow; ret->next=next;
80     return ret;
81 }
82 inline void link(int u, int v, int f)
83 {
84     e[u]=newedge(v, f, e[u]); e[v]=newedge(u, 0, e[v]);
85     e[u]->pair=e[v]; e[v]->pair=e[u];
86 }
87 inline bool bfs()
88 {
89     static int q[sizeOfPoint];
90     static int l, r;
91     memset(h, 0xFF, sizeof(h)); h[T]=0;
92     l=r=0;
93     for (q[r++]=T;l<r;l++)
94     {
95         int u=q[l];
96         ++gap[h[u]];
97         for (edge * i=e[u];i;i=i->next) if (h[i->point]==-1)
98         {
99             h[i->point]=h[u]+1;
100             q[r++]=i->point;
101         }
102     }
103     return h[S]>-1;
104 }
105 inline int isap()
106 {
107     static edge * t[sizeOfPoint], * p[sizeOfPoint];
108     static int aug[sizeOfPoint];
109     int flow=0, hmin=0;
110
111     if (!bfs()) return 0;
112
113     memcpy(t, e, sizeof(e)); memset(p, 0, sizeof(p));
114     aug[S]=inf;
115     for (int u=S;h[S]<V; )
116     {
117         if (u==T)
118         {
119             flow+=aug[T];
120             for (edge * i=p[T];i;i=p[i->point])
121                 aug[i->point]-=aug[T], i->pair->flow-=aug[T], i->flow+=aug[T];
122             for (edge * i=p[T];i;i=p[i->point]) if (aug[i->point])
123             {
124                 u=i->point;
125                 break;
126             }
127         }
128
129         edge *& i=t[u];
130         for ( ;i && (!i->flow || h[i->point]+1!=h[u]);i=i->next);
131         if (i)
132         {
133             aug[i->point]=min(aug[u], i->flow); p[i->point]=i->pair;
134             u=i->point;
135         }
136         else
137         {
138             if (!--gap[h[u]]) break;
139             hmin=V;
140             for (edge * j=e[u];j;j=j->next) if (j->flow && h[j->point]+1<hmin)
141             {
142                 hmin=h[j->point]+1;
143                 t[u]=j;
144             }
145             ++gap[h[u]=hmin];
146             u=u==S?S:p[u]->point;
147         }
148     }
149
150     return flow;
151 }
152 inline seg * newseg(seg * t)
153 {
154     seg * newt=port_seg++;
155     newt->p=++V; newt->l=t?t->l:NULL; newt->r=t?t->r:NULL;
156     return newt;
157 }
158 seg * insert(seg * t, int l, int r, int p, int v)
159 {
160     seg * newt=newseg(t);
161     if (l==r)
162     {
163         if (t) link(newt->p, t->p, inf);
164         link(newt->p, v, inf);
165     }
166     else
167     {
168         int m=(l+r)>>1;
169         if (p<=m)
170         {
171             newt->l=insert(newt->l, l, m, p, v), link(newt->p, newt->l->p, inf);
172             if (newt->r) link(newt->p, newt->r->p, inf);
173         }
174         else
175         {
176             newt->r=insert(newt->r, m+1, r, p, v), link(newt->p, newt->r->p, inf);
177             if (newt->l) link(newt->p, newt->l->p, inf);
178         }
179     }
180
181     return newt;
182 }
183 void query(seg * t, int l, int r, int ql, int qr, int v)
184 {
185     if (!t) return ;
186     if (l==ql && r==qr) link(v, t->p, inf);
187     else
188     {
189         int m=(l+r)>>1;
190         if (qr<=m) query(t->l, l, m, ql, qr, v);
191         else if (ql>=m+1) query(t->r, m+1, r, ql, qr, v);
192         else query(t->l, l, m, ql, m, v), query(t->r, m+1, r, m+1, qr, v);
193     }
194 }