|
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669 |
java提交注意package#pragma comment(linker, "/STACK:1024000000,1024000000")kmpvoid
Next(int
n){ int
j=0,k=-1; next[0]=-1; while(j<n){ if(k==-1||org[j]==org[k]){ j++;k++; if(org[j]!=org[k])next[j]=k; else
next[j]=next[k]; } else
k=next[k]; } return;}int
search(int
N,int n){//a为主串，b为模式串 int
i=0,j=0; while(i<N&&j<n){ if(j==-1||a[i]==b[j]){i++;j++;} else
j=next[j]; } if(j>=n)return
i-n; else
return -1;}快速读入/* 可以负数，不能小数*/inline
void inp( int
&n ){ n=0; int
ch=getchar_unlocked(),sign=1; while( ch < ‘0‘
|| ch > ‘9‘
){if(ch==‘-‘)sign=-1; ch=getchar_unlocked();} while( ch >= ‘0‘
&& ch <= ‘9‘
) n=(n<<3)+(n<<1)+ ch-‘0‘, ch=getchar_unlocked(); n=n*sign;}树状数组二维树状数组/* 二维树状数组，low求低位，update向后更新，query查询 update(x,y,num):x、y横纵坐标，num加数 query(x,y)：x,y横纵坐标，返回从1,1到x,y和，int范围*/inline
int low(int
x){ return
x&-x;}void
update(int
x,int y,int num){ int
Y=y; while(x<=n){ y=Y; while(y<=n){ sum[x][y]+=num; y+=low(y); } x+=low(x); }}int
query(int
x,int y){ int
Y=y,ans=0; while(x>0){ y=Y; while(y>0){ ans+=sum[x][y]; y-=low(y); } x-=low(x); } return
ans;}线段树/*矩形周长，线段树*/#define maxn 5005#define lson l,m,rt<<1#define rson m,r,rt<<1|1struct
Node{ int
num,len,lnum,lazy; //num为此线段覆盖次数，len为覆盖长度，lnum为段数，lazy为延迟数 bool
lc,rc; //表示线段两端有无被覆盖};struct
Line{ int
l,r,y; bool
up;};Line line[maxn<<1];Node node[maxn<<2];int
num,x[maxn<<1];void
pushup(int
rt){//向上更新 node[rt].len=node[rt<<1].len+node[rt<<1|1].len; node[rt].lnum=node[rt<<1].lnum+node[rt<<1|1].lnum; node[rt].lc=node[rt<<1].lc; node[rt].rc=node[rt<<1|1].rc; node[rt].num=max(node[rt<<1].num,node[rt<<1|1].num); if(node[rt<<1].rc&&node[rt<<1|1].lc) node[rt].lnum--;//如果左孩子的右节点和右孩子的左节点都被标记，则线段数减1 return;}void
pushdown(int
rt,int
l,int r){//向下更新 if(node[rt].lazy){ int
m=l+r>>1; node[rt<<1].len=x[m-1]-x[l-1]; node[rt<<1|1].len=x[r-1]-x[m-1]; node[rt<<1].num+=node[rt].lazy; node[rt<<1|1].num+=node[rt].lazy; node[rt<<1].lazy+=node[rt].lazy; node[rt<<1|1].lazy+=node[rt].lazy; if(node[rt<<1].num>0) node[rt<<1].lnum=node[rt<<1].lc=node[rt<<1].rc=1; elsenode[rt<<1].num=node[rt<<1].len=node[rt<<1].lnum=node[rt<<1].lc=node[rt<<1].rc=0; //如果覆盖数为0，则删除 if(node[rt<<1|1].num>0) node[rt<<1|1].lnum=node[rt<<1|1].lc=node[rt<<1|1].rc=1; else
node[rt<<1|1].num=node[rt<<1|1].len=node[rt<<1|1].lnum=node[rt<<1|1].lc=node[rt<<1|1].rc=0; } node[rt].lazy=0;}void
add(int
L,int R,int l,int r,int rt){//增加线段 if(L<=l&&R>=r){ node[rt].len=x[r-1]-x[l-1]; node[rt].num++; node[rt].lc=node[rt].rc=node[rt].lnum=1; node[rt].lazy++;//延迟更新 return; } pushdown(rt,l,r); int
m=(l+r)>>1; if(L<m)add(L,R,lson); if(R>m)add(L,R,rson); pushup(rt); return;}void
del(int
L,int R,int l,int r,int rt){//删除线段 if(L<=l&&R>=r){ node[rt].num--; if(node[rt].num<=0){ node[rt].len=0; node[rt].lc=node[rt].rc=node[rt].lnum=0; node[rt].num=0; node[rt].lazy--;//如果此线段被删除，延迟更新子线段 return; } if(r-l==1)return; } pushdown(rt,l,r); int
m=(l+r)>>1; if(L<m)del(L,R,lson); if(R>m)del(L,R,rson); pushup(rt); return;}bool
cmp(Line a,Line b){ if(a.y==b.y) return
a.l<b.l; else
return a.y<b.y;}inline
int find(int
key){//查询x坐标对应的下标，因为线段树要求从1开始，所以下标加1 return
lower_bound(x,x+num,key)-x+1;}int
main(){ int
n,i,x1,x2,y1,y2; scanf("%d",&n); num=0; for(i=0;i<n;i++){ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x[num++]=x1;x[num++]=x2; line[i<<1].l=x1;line[i<<1].r=x2;line[i<<1].y=y1;line[i<<1].up=1; line[i<<1|1].l=x1;line[i<<1|1].r=x2;line[i<<1|1].y=y2;line[i<<1|1].up=0; } sort(x,x+num);//对x排序，离散化处理 num=unique(x,x+num)-x;//去重 n=n<<1; sort(line,line+n,cmp); int
pre=0,ans=0; for(i=0;i<n-1;i++){ if(line[i].up)//如果是下边，则加边 add(find(line[i].l),find(line[i].r),1,num,1); else
//如果是上边，则删除 del(find(line[i].l),find(line[i].r),1,num,1); ans+=node[1].lnum*(line[i+1].y-line[i].y)*2;//平行y轴 ans+=abs(node[1].len-pre);//平行x轴 pre=node[1].len; } del(find(line[i].l),find(line[i].r),1,num,1); ans+=abs(node[1].len-pre); printf("%d\n",ans);}无向图重联通分量/** 无向图重联通分量 Tarjan n^2*/stack<int> S;void
dfs(int
v,int f){ vis[v]=1; dph[v]=low[v]=d++; S.push(v); for(int
i=0; i<org[v].size(); i++){ int
u=org[v][i]; if(u==f)continue; if(vis[u]==1)low[v]=min(low[v],dph[u]); else
if(!vis[u]){ dfs(u,v); low[v]=min(low[v],low[u]); if(low[u]>=dph[v]){//u为关节点 num++; belong[v].pb(num);belong[u].pb(num); while(S.top()!=u){// 注意边界，如果吧push放在for循环里就是!=v不用pop，否则就是!=u最后还要pop belong[S.top()].pb(num); S.pop(); } S.pop(); } } } vis[v]=2;}int
Tarjan() //搜索重联通分量{ num=0; while(!S.empty())S.pop(); for(int
i=1; i<=n; i++){ d=0; if(!vis[i]) dfs(i,-1); }}最大流 Dinic/*Dinic n^2*m 当前弧+GAP*/#define INF 999999999#define maxm 900000#define maxn 1000int
n,s,t,flow;struct
edge{ int
v,c,f,next;}e[maxm];int
first[maxn],cnt,cur[maxn],d[maxn],S,E;//S起点E终点bool
vis[maxn];queue<int> q;inline
void addedge( int
u, int
v, int
w ){ e[cnt].v = v; e[cnt].c = w; e[cnt].f = 0;e[cnt].next = first[u]; first[u] = cnt++; e[cnt].v = u; e[cnt].c = 0; e[cnt].f = 0;e[cnt].next = first[v]; first[v] = cnt++;}int
BFS(){ int
u,v; while
( !q.empty())q.pop(); q.push(S); memset(vis,0,sizeof(vis)); d[s] = 0; vis[s] = 1; while
( !q.empty() ) { u = q.front(); q.pop(); for
( int i = first[u]; ~i; i = e[i].next ) { v = e[i].v; if
( !vis[v] && e[i].c > e[i].f ) { vis[v] = 1; q.push(v); d[v] = d[u] + 1; } } } return
vis[t];}int
DFS( int
u, int
a ){ if
( u == E || a == 0 ) return
a; int
fl = a,v,f; for
( int &i = cur[u]; ~i ; i = e[i].next ){ //i为cur[u]引用，当前弧优化 v = e[i].v; if
( d[u] + 1 == d[v] && ( f = DFS( v, min( a, e[i].c - e[i].f ) ) ) > 0 ) { e[i].f += f; e[i^1].f -= f; fl -= f; if
( !fl ) return
a; } } return
a-fl;}int
dinic(int
s,int e){ S=s;E=e; int
flow=0; while
( BFS() ){ for
( int i = 1; i <= n; ++i ) cur[i] = first[i]; flow += DFS(s,INF); } return
flow;}HLPP/*HLPP n^2*m^0.5 有GAP优化*/#define Maxn 205#define Maxm 160005int
first[Maxn],d[Maxn],cnt,re[Maxn];int
num[Maxn];//判断断层int
KN;//汇点可以到达的最大标号bool
vis[Maxn];int
S,E;queue<int> q;struct
node { int
ind; bool
operator<(const
node &a) const
{ return
d[ind]<d[a.ind]; } node(int
&x):ind(x) {}};priority_queue<node> order; //HL优化效果不明显struct
edge { int
v,c,f,next;} e[Maxm];inline
void add(int
&a,int
&b,int
c){ e[cnt].v=b; e[cnt].c=c; e[cnt].f=0; e[cnt].next=first[a]; first[a]=cnt++; e[cnt].v=a; e[cnt].c=0; e[cnt].f=0; e[cnt].next=first[b]; first[b]=cnt++;}void
init() { while(!q.empty())q.pop(); while(!order.empty())order.pop(); memset(vis,0,sizeof(vis)); memset(num,0,sizeof(num)); KN=E; vis[E]=vis[S]=1; d[E]=0; d[S]=E; q.push(E); int
i,u,v; while(!q.empty()) { u=q.front(); q.pop(); for(i=first[u]; ~i; i=e[i].next) { v=e[i].v; if(!vis[v]) { d[v]=d[u]+1; num[d[v]]++; vis[v]=1; q.push(v); } } } memset(re,0,sizeof(re));memset(vis,0,sizeof(vis)); vis[S]=vis[E]=1; for(i=first[S]; ~i; i=e[i].next){ v=e[i].v; re[v]+=e[i].c; e[i].f=e[i].c; e[i^1].f=-e[i].c; if(!vis[v]) order.push(v); vis[v]=1; }}int
deal(){ int
u,v,Min,t,ii,f,i; while(!order.empty()) { u=order.top().ind; order.pop(); if(d[u]>KN)continue; //不关心可行流，只关心结果，因此不用退回 vis[u]=0; while(re[u]>0) { Min=1E9; for(i=first[u]; ~i; i=e[i].next){ if(e[i].c==e[i].f)continue; t=e[i].v; if(d[t]+1==d[u]){ v=t;ii=i;break; } else
if(Min>d[t]) v=t,ii=i,Min=d[t]; } if(i==-1){ if(--num[d[u]]==0) KN=min(KN,d[u]-1); //出现断层，更新最大标号 d[u]=Min+1; } f=min(re[u],e[ii].c-e[ii].f); re[u]-=f; re[v]+=f; e[ii].f+=f; e[ii^1].f-=f; if(!vis[v])order.push(v); vis[v]=1; } } return
re[E];}int
HLPP(int
s,int e){ S=s;E=e; init(); return
deal();}最小费用流(Primal-Dual)/*最小费用流 (Primal-Dual) */struct
edge{ int
cost, cap, v, next;}e[MAXM];int
first[MAXN], cnt;int
vis[MAXN], d[MAXN];int
ans, cost, src, des, n;void
init(){ memset(first, -1, sizeof(first)); cnt=ans=cost=0;}void
add(int
u, int
v, int
cap, int
cost){ e[cnt].v = v; e[cnt].cap = cap; e[cnt].cost = cost; e[cnt].next = first[u]; first[u] = cnt++; e[cnt].v = u; e[cnt].cap = 0; e[cnt].cost = -cost; e[cnt].next = first[v]; first[v] = cnt++;}int
aug(int
u, int
f){ if(u == des){ ans += cost * f; return
f; } vis[u] = 1; int
flow=f,t; for(int
i = first[u]; ~i; i = e[i].next) if(e[i].cap && !e[i].cost && !vis[e[i].v]){ t = aug(edge[i].v, min(tmp,edge[i].cap)); edge[i].cap -= t; edge[i^1].cap += t; flow -= t; if(!flow) return
f; } return
f-flow;}deque<int>Q;bool
modlabel(){ //SPFA 增广 for(int
i = 0; i <= n; i++) d[i] = INF; d[des] = 0; whlie(!Q.empty())Q.pop(); Q.push_back(des); while(!Q.empty()){ int
u = Q.front(), tmp; Q.pop_front(); for(int
i = first[u]; ~i ; i = e[i].next) if(e[i^1].cap && (tmp = d[u] - e[i].cost) < d[e[i].v]) (d[e[i].v] = tmp) <= d[Q.empty() ? src : Q.front()] ? Q.push_front(e[i].v) : Q.push_back(e[i].v); } for(int
u = 1; u <= n; u++) for(int
i = first[u]; i != -1; i = e[i].next) e[i].cost += d[e[i].v] - d[u]; cost += d[src]; return
d[src] < INF;}void
costflow(){ while(modlabel()){ do
memset(vis, 0, sizeof(vis)); while(aug(src, INF)); }}Zwk 适合最终流量大 费用范围不大 或增广路短的图 非负权值/*zwk KM重标号 增广路同上，sap 不能用于负权值路*/bool
modlabel(){ int
delta = INF; for(int
u = 1; u <= n; u++) if(vis[u]) for(int
i = first[u]; ~i ; i = e[i].next) if(e[i].cap && !vis[e[i].v] && e[i].cost < delta) delta = e[i].cost; if(delta == INF) return
false; for(int
u = 1; u <= n; u++) if(vis[u]) for(int
i = first[u]; ~i ; i = e[i].next) edge[i].cost -= delta, edge[i^1].cost += delta; cost += delta; return
true;}void
costflow(){ do{ do
memset(vis, 0, sizeof(vis)); while(aug(src, INF)); }while(modlabel());}最短路SPFA/** 复杂度分析： 普通SPFA km kmax=n 不适合稠密图 一般为2 优先级队列 加入节点复杂度logn 节点数太多时适得其反，对于特殊数据速度略小于普通spfa 对于随机图效果很好 手动模拟SLF，LLL 复杂度低于优先级队列，最坏情况与普通SPFA持平*/#define Maxn 100010//最大点数#define Maxm 400010//最大边数，无向图要建双向边int
w[Maxm],u[Maxm],next[Maxm],cnt;int
first[Maxn],havein[Maxn];//havin为入队次数long
long d[Maxn];//距离int
n;bool
in[Maxn];//队中标志inline
void add(int
vn,int
un,int
wn){//邻接表存储 u[cnt]=un;w[cnt]=wn;next[cnt]=first[vn];first[vn]=cnt++;}struct
node{ int
v,dd; node(int
&a):v(a),dd(d[a]){}; bool
operator< (const
node& a)const{ return
dd>a.dd; }};priority_queue<node> q; //利用优先级队列SLF和LLLbool
spfa(int
s){ int
i,now,ne,t; memset(in,0,sizeof(in)); memset(havein,0,sizeof(havein)); for(i=0;i<n;i++)d[i]=INF; //memset(d,0x3f,sizeof(d)); d[s]=0;in[s]=1;q.push(s); while(!q.empty()){ now=q.top().v;q.pop(); if(!in[now])continue; in[now]=0; for(i=first[now];~i;i=next[i]){ ne=u[i]; if(d[ne]<=(t=d[now]+w[i]))continue; d[ne]=t; in[ne]=1; q.push(ne); if(++havein[ne]>n)return
0;//判断有无负环 } } return
1;//返回1为正常，0为有负环}#define M 200000 //手动模拟int
q[M];bool
spfa(int
s){ int
i,now,ne,t; memset(in,0,sizeof(in)); memset(havein,0,sizeof(havein)); memset(d,0x3f,sizeof(d)); int
l,r,len;l=r=len=0; long
long sum=0; d[s]=0;in[s]=havein[s]=1; q[r++]=s;len++; while(l!=r){ now=q[l++]; if(l==M)l=0; if(d[now]*len>sum){//LLL q[r++]=now; if(r==M)r=0; continue; } len--; sum-=d[now]; in[now]=0; for(i=first[now];~i;i=Next[i]){ ne=u[i]; if(d[ne]<=(t=d[now]+w[i]))continue; d[ne]=t; if(in[ne])continue; in[ne]=1; if(t<=d[q[l]]){ //SLF if(--l<0)l=M-1; q[l]=ne; } else{ q[r++]=ne; if(r==M)r=0; } len++; sum+=t; if(++havein[ne]>n)return
0; } } return
1;//返回1为正常，0为有负环}void
init()//边初始化{ cnt=0; memset(first,-1,sizeof(first));}dijkstra/*dijkstra 复杂度M+NlgN*/struct
node{ double
dis; int
v; node(int
&a):v(a),dis(d[a]){} bool
operator <(const
node &b)const{ if(dis==b.dis)return
n>b.n; return
dis>b.dis;//注意符号！！这是降序排列 }};priority_queue<node> q;void
dijkstra(int
s){ while(!q.empty())q.pop(); int
i,x; memset(vis,0,sizeof(vis)); memset(d,0x3f,sizeof(d)); d[s]=0; q.push(s); while(!q.empty()){ x=q.top().v;q.pop(); if(now.dis!=dis[x]||vis[x])continue; vis[x]=1; for(i=1;i<=n;i++){ if(!vis[i]&&dis[i]>dis[x]+map[x][i]){ dis[i]=dis[x]+map[x][i]; q.push(i); } } } return;}拓扑排序/**拓扑排序 n^2 递归版 注意爆栈*/int
inq[Maxn];int
topo[Maxn],t;//topo为结果序列bool
dfs(int
u){ inq[u]=-1;//正在队列中 for(int
v=0;v<n;v++) if(G[u][v]){ //邻接矩阵 if(inq[v]<0)return
0;//存在有向环 else
if(!inq[v]&&!dfs(v))return
0; } inq[u]=1;topo[--t]=u; return
1;}bool
toposort(){ t=n; memset(inq,0,sizeof(inq)); for(int
u=0;u<n;u++) if(!inq[u]&&!dfs(u))return
0; return
1;}/*循环版 需要统计入度*/int
in[Maxn];//节点入度int
st[Maxn],cnt;//记录入度为0的点栈bool
toposort(){ for(int
i=n,now; i>=1; i--){ //节点数 if(cnt==0)return
0;//没有入度为0的节点 now=st[--cnt]; for(int
nn=1; nn<=n; nn++) if(map[now][nn]&&(--in[nn])==0)st[cnt++]=nn; in[now]=i; ans[i]=now; } return
1;}最大匹配/**二分图最大匹配：Hopcroft-Karp算法复杂度：N^0.5 * M*///对于要匹配的点 分为x集合的点，和y集合的点int
Mx[MAX],My[MAX];//那么这里的Mx[i]的值表示x集合中i号点的匹配点，My[j]的值就是y集合j点匹配的点int
dx[MAX],dy[MAX];//这里就是bfs找增广路用的数组 对于u-->v可达就有dy[v] = dx[u] + 1int
vis[MAX],dis;//辅助queue<int>Q;bool
bfs() //最短增广路{ int
i ,v,u; dis = INF; while(!Q.empty())q.pop(); memset(dx,-1,sizeof(dx)); memset(dy,-1,sizeof(dy)); for(i = 0; i < m ;i ++) // 寻找x中未匹配的 if(Mx[i] == -1) Q.push(i),dx[i] = 0; while(!Q.empty()){ u = Q.front(); Q.pop(); if(dx[u] > dis) break; for(i = head[u]; i != -1; i = edge[i].next){ v = edge[i].to; if(dy[v] == -1){ dy[v] = dx[u] + 1; if(My[v] == -1) dis = dy[v]; else{ dx[My[v]] = dy[v] + 1; Q.push(My[v]); } } } } return
dis != INF;}bool
dfs(int
u){ int
v; for(int
i = head[u]; i != -1; i = edge[i].next){ v = edge[i].to; if(!vis[v] && dy[v] == dx[u] + 1){ vis[v] = 1; if(My[v] != -1 && dy[v] == dis) continue; if(My[v] == -1 || dfs(My[v])){ Mx[u] = v; My[v] = u; return
true; } } } return
false;}int
match(){ int
ans = 0; memset(Mx,-1,sizeof(Mx)); memset(My,-1,sizeof(My)); while(bfs()){ memset(vis,0,sizeof(vis)); for(int
u = 0; u < m; u ++) if(Mx[u] == -1 && dfs(u))//这里特别要注意，Mx[u] == -1 && dfs(u)先后顺序千万不能换，dfs之后Mx[u]就会变化 ans ++; } return
ans;} |
原文：http://www.cnblogs.com/czjxy881/p/3552632.html