寒假时没事写了这几个代码，算是我几个月后重操键盘了。这是几道经典题目，可能有人需要，再加上昨天搞JavaScript改过去改过来把PJBlog改得面目全非终于实现了代码高亮忍不住想Show一下，于是把这些代码（连同题目）发了上来。
标准的网络流题目代码
Problem : goods
货物运输
问题描述
你第一天接手一个大型商业公司就发生了一件倒霉的事情：公司不小心发送了一批次品。很不幸，你发现这件事的时候，这些次品已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批次品要发给哪个零售商，但是要把这批次品送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输货物。在追查这些次品的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，在保证次品无法送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。
输入格式
第一行：两个用空格分开的整数N(0<=N<=200)和M(2<=M<=200)。N为运输卡车的数目，M为仓库的数目。1号仓库是公司发货的出口，仓库M属于零售商。
第二行到第N+1行：每行有三个整数，Si、Ei和Ci。Si和Ei(1<=Si,Ei<=M)分别表示这辆卡车的出发仓库和目的仓库，Ci(0<=Ci<=10,000,000)是让这辆卡车停止运输的损失。
输出格式
输出一个整数，即最小的损失数。
样例输入
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
样例输出
50
样例说明
40
1——>2
| /|
| / |
20| / |30
| 20 |
| / |
| / |
/_ V
4<——3
10
如图，停止1->4、2->4、3->4三条卡车运输线路可以阻止货物从仓库1运输到仓库4，代价为20+20+10=50。
数据规模
对于50%的数据，N,M<=25
对于100%的数据，N,M<=200
program goods;
const
MaxN=200;
MaxM=200;
Infinite=Maxlongint;
type
rec=record
node,father:integer;
minf:longint;
end;
var
f,c:array[1..MaxN,1..MaxN]of longint;
queue:array[1..MaxN]of rec;
hash:array[1..MaxN]of boolean;
n,m,closed,open:integer;
procedure readp;
var
i,x,y:integer;
t:longint;
begin
readln(m,n);
for i:=1 to m do
begin
readln(x,y,t);
c[x,y]:=c[x,y]+t;
end;
end;
function FindPath:boolean;
procedure Init;
begin
fillchar(hash,sizeof(hash),0);
fillchar(queue,sizeof(queue),0);
closed:=0;
open:=1;
queue[1].node:=1;
queue[1].father:=0;
queue[1].minf:=Infinite;
hash[1]:=true;
end;
function min(a,b:longint):longint;
begin
if a<b then min:=a
else min:=b;
end;
var
i,NodeNow:integer;
begin
Init;
repeat
inc(closed);
NodeNow:=queue[closed].node;
for i:=1 to n do if not hash[i] then
if (f[NodeNow,i]<c[NodeNow,i]) then
begin
inc(open);
queue[open].node:=i;
queue[open].father:=closed;
queue[open].minf:=min(queue[closed].minf,c[NodeNow,i]-f[NodeNow,i]);
hash[i]:=true;
if i=n then exit(true);
end;
until closed>=open;
exit(false);
end;
procedure AddPath;
var
i,j:integer;
delta:longint;
begin
delta:=queue[open].minf;
i:=open;
repeat
j:=queue[i].father;
inc(f[queue[j].node,queue[i].node],delta);
dec(f[queue[i].node,queue[j].node],delta);
i:=j;
until i=0;
end;
procedure writep;
var
i:integer;
ans:longint=0;
begin
for i:=1 to n do
ans:=ans+f[1,i];
writeln(ans);
end;
{====main====}
begin
assign(input,'goods.in');
reset(input);
readp;
close(input);
while FindPath do AddPath;
assign(output,'goods.out');
rewrite(output);
writep;
close(output);
end.
统计逆序对 Treap版
Problem : inverse
逆序对
问题描述
在一个排列中，前面出现的某个数比它后面的某个数大，即当Ai>Aj且i<j时，则我们称Ai和Aj为一个逆序对。给出一个1到N的排列，编程求出逆序对的个数。
输入格式
第一行输入一个正整数N；
第二行有N个用空格隔开的正整数，这是一个1到N的排列。
输出格式
输出输入数据中逆序对的个数。
样例输入
4
3 1 4 2
样例输出
3
样例说明
在输入数据中，(3,1)、(3,2)和(4,2)是仅有的三个逆序对。
数据规模
对于30%的数据，N<=1000；
对于100%的数据，N<=100 000。
program inverse;
const
MaxH=Maxlongint;
type
p=^rec;
rec=record
v,s,h:longint;
left,right:p;
end;
var
header:p=nil;
ans:int64=0;
procedure CalcuS(var w:p);
begin
w^.s:=1;
if w^.right<>nil then inc(w^.s,w^.right^.s);
if w^.left<>nil then inc(w^.s,w^.left^.s);
end;
function RotateLeft(w:p):p;
var
tmp:p;
begin
tmp:=w^.left;
w^.left:=tmp^.right;
tmp^.right:=w;
exit(tmp);
end;
function RotateRight(w:p):p;
var
tmp:p;
begin
tmp:=w^.right;
w^.right:=tmp^.left;
tmp^.left:=w;
exit(tmp);
end;
function Insert(a:longint;w:p):p;
begin
if w=nil then
begin
new(w);
w^.v:=a;
w^.h:=random(MaxH);
w^.s:=1;
w^.left:=nil;
w^.right:=nil;
end
else if a<w^.v then
begin
ans:=ans+1;
if w^.right<>nil then ans:=ans+w^.right^.s;
w^.left:=Insert(a,w^.left);
if w^.left^.h<w^.h then
begin
w:=RotateLeft(w);
CalcuS(w^.right);
end else
CalcuS(w^.left);
end
else if a>w^.v then
begin
w^.right:=Insert(a,w^.right);
if w^.right^.h<w^.h then
begin
w:=RotateRight(w);
CalcuS(w^.left);
end else
CalcuS(w^.right);
end;
exit(w);
end;
{====main====}
var
n,i,t:longint;
begin
randseed:=2910238;
assign(input,'inverse.in');
reset(input);
readln(n);
for i:=1 to n do
begin
read(t);
header:=Insert(t,header);
end;
close(input);
assign(output,'inverse.out');
rewrite(output);
writeln(ans);
close(output);
end.
USACO经典题目：矩形颜色（离散化+扫描）
Problem : rect
矩形颜色
问题描述
N个不同颜色的不透明长方形(1<=N<=1000)被放置在一张宽为A长为B的白纸上。这些长方形被放置时，保证了它们的边与白纸的边缘平行。所有的长方形都放置在白纸内，所以我们会看到不同形状的各种颜色。坐标系统的原点(0,0)设在这张白纸的左下角，而坐标轴则平行于边缘。
输入数据
每行输入的是放置长方形的方法。第一行输入的是那个放在最底下的长方形（即白纸）。
第一行：A、B和N，由空格分开(1<=A,B<=10,000)
第二到N+1行：每行为五个整数llx,lly,urx,ury,color。这是一个长方形的左下角坐标，右上角坐标和颜色。颜色1和底部白纸的颜色相同。
输出数据
输出文件应该包含一个所有能被看到的颜色连同该颜色的总面积的清单（即使颜色的区域不是连续的），按color的增序顺序。
不要打印出最后不能看到的颜色。
样例输入
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4
样例输出
1 91
2 84
3 187
4 38
数据规模
对于50%的数据，A,B<=300，N<=60；
对于100%的数据，A,B<=10000，N<=1000。
program rect;
const
MaxN=1000; { Rect number in the Worst Case }
MaxCol=1000; { Color number in the Worst Case }
Infinity=Maxint; { Set to be Heap[0] }
type
RecSeg=record
y,x1,x2,order:integer;
end;
var
xar,heap:array[0..MaxN*2+2]of integer; { Array of All X-Value and Heap, respectively }
color:array[1..MaxN+1]of integer; { Index of Color corresponding to order}
ans:array[1..MaxCol]of longint; { Answers to be print }
seg:array[0..MaxN*2+2]of RecSeg; { Horizontal Segments }
hash:array[1..MaxN*2+2]of boolean; { Determine if a Segment has been scanned }
n,HeapSize:integer;
procedure SwapInt(var a,b:integer);
var
tmp:integer;
begin
tmp:=a;
a:=b;
b:=tmp;
end;
procedure SwapRec(var a,b:RecSeg);
var
tmp:RecSeg;
begin
tmp:=a;
a:=b;
b:=tmp;
end;
procedure DataInsert(start,x1,y1,x2,y2,col,order:integer);
var
tmp:RecSeg;
begin
xar[start]:=x1;
xar[start+1]:=x2;
color[start div 2+1]:=col;
tmp.order:=order;
tmp.y:=y1;
tmp.x1:=x1;
tmp.x2:=x2;
seg[start]:=tmp;
tmp.y:=y2;
seg[start+1]:=tmp;
end;
procedure Readp;
var
a,b,x1,x2,y1,y2,col,i:integer;
begin
readln(a,b,n);
n:=n+1;
DataInsert(1,0,0,a,b,1,1);
for i:=2 to n do
begin
readln(x1,y1,x2,y2,col);
DataInsert(2*i-1,x1,y1,x2,y2,col,i);
end;
end;
procedure SortXar;
var
i,j:integer;
begin
for i:=1 to 2*n do
for j:=1 to 2*n-1 do
if xar[j]>xar[j+1] then SwapInt(xar[j],xar[j+1]);
end;
procedure SortSeg;
var
i,j:integer;
begin
for i:=1 to 2*n do
for j:=1 to 2*n-1 do
if seg[j].y>seg[j+1].y then SwapRec(seg[j],seg[j+1]);
end;
procedure HeapInsert(x:integer);
var
w:integer;
begin
inc(HeapSize);
w:=HeapSize;
while Heap[w shr 1]<x do
begin
Heap[w]:=Heap[w shr 1];
w:=w shr 1;
end;
Heap[w]:=x;
end;
procedure HeapDelete;
var
&n
bsp; x:integer;
w:integer=1;
begin
x:=Heap[HeapSize];
dec(HeapSize);
while w shl 1<=HeapSize do
begin
w:=w shl 1;
if (w<>HeapSize) and (Heap[w+1]>Heap[w]) then inc(w);
if Heap[w]>x then Heap[w shr 1]:=Heap[w]
else begin
w:=w shr 1;
break;
end;
end;
Heap[w]:=x;
end;
procedure Scan(x1,x2:integer);
var
i:integer;
j:integer=0;
begin
for i:=1 to 2*n do if (seg[i].x1<=x1) and (seg[i].x2>=x2) then
begin
inc(ans[Color[Heap[1]]],(x2-x1)*(seg[i].y-seg[j].y));
hash[seg[i].order]:=not hash[seg[i].order];
if hash[seg[i].order] then HeapInsert(seg[i].order)
else while (HeapSize>0) and not hash[Heap[1]] do HeapDelete;
j:=i;
end;
end;
procedure Solve;
var
i:integer;
begin
for i:=1 to 2*n-1 do if xar[i]<xar[i+1] then
begin
fillchar(Heap,Sizeof(Heap),0);
fillchar(hash,Sizeof(hash),0);
HeapSize:=0;
Heap[0]:=Infinity;
Scan(xar[i],xar[i+1]);
end;
end;
procedure Writep;
var
i:integer;
begin
for i:=1 to MaxCol do
if ans[i]>0 then writeln(i,' ',ans[i]);
end;
{====main====}
begin
assign(input,'rect.in');
reset(input);
assign(output,'rect.out');
rewrite(output);
Readp;
SortXar;
SortSeg;
Solve;
Writep;
close(input);
close(output);
end.
这几天大家发现我改PJBlog改错了什么东西导致Bug的话麻烦帮忙报告一下。事实上很有可能有人发现有Bug但是不能报告，因为我很有可能把验证码系统也搞坏了。
如果这几天大家没有发现问题的话，我把这几天我的PJBlog个性修改方法和心得写出来分享一下（越来越喜欢搞Web Design了）。
做人要厚道
转贴请注明出处
（这篇日志没什么技术含量，感觉写上这两句很别扭）