2部图匹配,不能考虑0
Program P1325;
var
n,m,k,i,j:longint;
p,x,y,level:longint;
map,f,list:array[-1..300,-1..300] of longint;
d,e:array[-1..300] of longint;
queue:array[1..300] of longint;
b:array[-1..300] of boolean;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure dijstra;
var
h,t,i:longint;
begin
fillchar(d,sizeof(d),0);
fillchar(queue,sizeof(queue),0);
fillchar(b,sizeof(b),false);
queue[1]:=n+m;
b[n+m]:=true;
h:=1;
t:=1;
while h<=t do
begin
for i:=-1 to n+m-1 do
begin
if (map[i,queue[h]]>0) then
if (not(b[i])) then
begin
inc(t);
queue[t]:=i;
b[i]:=true;
d[i]:=d[queue[h]]+1;
end;
end;
inc(h);
end;
d[-1]:=n+m+2+1;
end;
procedure push(i,j:longint);
var
flow:longint;
begin
flow:=min(e[i],map[i,j]-f[i,j]);
if (e[j]=0) and (j>-1) and (j<n+m) then
begin
inc(list[d[j],0]);
list[d[j],list[d[j],0]]:=j;
level:=max(level,d[j]);
end;
dec(e[i],flow);
inc(e[j],flow);
inc(f[i,j],flow);
f[j,i]:=-f[i,j];
end;
procedure relable(i:longint);
var
j,minj:longint;
begin
minj:=maxlongint;
for j:=-1 to n+m do
if (map[i,j]-f[i,j]>0) and (b[j]) then minj:=min(minj,d[j]);
d[i]:=minj+1;
level:=d[i];
inc(list[level,0]);
list[level,1]:=i;
end;
Procedure hllp;
var
i,j,flow:longint;
begin
dijstra;
level:=0;
for i:=0 to n-1 do
if b[i] then
begin
e[i]:=1;
f[-1,i]:=1;
f[i,-1]:=-1;
inc(list[d[i],0]);
list[d[i],list[d[i],0]]:=i;
level:=max(level,d[i]);
end;
while (level>0) do
begin
i:=list[level,list[level,0]];
dec(list[level,0]);
while (level>0) and (list[level,0]=0) do dec(level);
for j:=-1 to n+m do
if (d[i]=d[j]+1) and (map[i,j]-f[i,j]>0) and (b[j]) then
begin
push(i,j);
if e[i]=0 then break;
end;
if e[i]>0 then relable(i);
end;
end;
begin
read(n);
while (n>0) do
begin
fillchar(list,sizeof(list),0);
fillchar(e,sizeof(e),0);
fillchar(f,sizeof(f),0);
read(m,k);
fillchar(map,sizeof(map),0);
for i:=1 to k do
begin
read(p,x,y);
if (x=0) or (y=0) then continue;
map[x,n+y]:=1;
end;
for i:=0 to n-1 do map[-1,i]:=1;
for i:=n to n+m-1 do map[i,n+m]:=1;
hllp;
writeln(e[n+m]);
read(n);
end;
end.
分享到:
相关推荐
poj openjudge 1111题最大正向匹配 提交ac
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
这是北京大学ACM也就是POJ2195的源代码,用的是最优匹配算法。
初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) ... (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) ......
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) ...sgu218 hcraft 二分图匹配验证 二分答案
3.5.3 二分图匹配 3.5.4 一般图匹配 3.5.5 匹配、边覆盖、独立集和顶点覆盖 3.5.6 最小费用流 3.5.7 应用问题 3.6 与平面和空间打交道的计算几何 3.6.1 计算几何基础 3.6.2 极限情况 3.6.3 平面扫描 3.6.4 凸包 ...
8.14 带权的最优二分图匹配 184 9.搜索算法概略 187 9.1 迭代深搜+IDA* 187 9.2 分之界限法(深搜) 189 9.3 A* 8数码问题( pascal ) 192 9.4 优先队列广搜 194 10.应用 197 10.1 Joseph问题 197 10.2 N皇后构造解 ...
leetcode 2 和 c 实践 C++ ###数据结构和算法 大批 加一: # 合并排序数组:# 排序 搜索 二分查找:代码、#、#、# ...二和:# ...2) ...字符串匹配: ...二的幂:# ...动态规划:LeetCode#xx、POJ#xx 后缀数组
poj: 顶级编码器: 代码力量: 间谍: 佐伊: 福伊: 紫外线: ltOJ: leetcode: 重复部分: 稀疏动态规划 分而治之的问题 图算法问题 试题 搜索问题、DFS、BFS 和切边 排序:堆排序 流算法。 : 布隆过滤器: 卢: ...
3.2.2 二维 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3 树链剖分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.3.1 点权 . . ....