SRC私闯物理组——解题报告
发表时间：2010-07-08 16:16:39 浏览(1721) 评论(0)
【题目叙述】
在NOI考挂之后，SRC希望能重演cccum神牛的传奇，于是在双哥不知情的情况下偷偷跑到了物理竞赛组学习
PhO（Physicis Olympiad）。由于离物理省赛时间不多了，加上SRC没怎么接触过物理竞赛，这其中遇到的重重困难可想而知。
物理竞赛中需要记背的公式、定理、物理常数非常之多，这对于记忆力不是很好的SRC来说是很大的挑战。虽然已经把所有的知识看过一遍，但SRC还是没有记清楚所有的这些东西。不过，有一点是肯定的，那就是SRC记住了每个公式大概是什么意思。比如有公式E=MC2，SRC会说：它的含义是动量守恒，或者是角动量守恒，或者是质能方程。而对于一个定理，比如机械能守恒定律，SRC会说：它的公式表示为C=λf，或者是Ep1+Ek1=Ep2+Ek2，或者是PV=nRT。你看，虽然SRC不能确定某些公式的具体含义或某些定理的公式，但是他会限定一个含义范围，而这个范围中一定包含了该公式或定理的正确解释。
可是，这还不够，物理竞赛中是不能答许多答案让判卷老师挑出一个正确解答的。因此SRC需要你的帮助。
他把他所记忆的公式和定理之间的对应关系告诉正在机房的你，请你帮忙编一个程序告诉他一个对应关系。这个关系应包含尽量多的公式与定理的一一对应。当然，可能有多个对应关系的公式与定理的一一对应数目是一样多且最多的，所以你只需输出字典序最小的一组对应关系即可。关于字典序最小的定义参看样例解释。
【输入格式】（cphop.in）
第一行是两个数n、m，n表示公式个数，m表示定理个数。
接下来一行有若干个单词，由空格分隔，为公式。注意，公式仅可能包含’A’..’Z’，’0’..’9’ 和’=’这37个字符。
接下来一行为若干个单词，由空格分隔，为定理。定理仅可能包含’a’..’z’这26个字符。
以上任何一个公式的长度不大于15，定理的长度不大于20。
接下来为一个数p,表示对应关系数目。
接下来p行为每行都是一个对应关系的具体描述，包括最多三个，最少两个单词，由空格分隔。假如第一个单词是一个公式，则接下来的单词表示的是一些定理，也就是SRC认为该公式的含义为该行给出的定理之一。反过来，如果第一个单词是一个定理，那么下面的单词就是公式。这个你不必验证。
【输出格式】（cphop.out）
第一行为一个数，表示你找到了多少公式与定理之间的一一对应。
接下来若干行，每行由两个单词构成，第一个单词为一个公式，第二个单词为一个定理。是对你找到的对应关系的描述。
【样例输入】
3 3
E=MC2 PV=NRT F=MA
znfc nddedl lxqtfc
3
PV=NRT nddedl lxqtfc
znfc E=MC2
F=MA nddedl lxqtfc
【样例输出】
3
E=MC2 znfc
PV=NRT nddedl
F=MA lxqtfc
解释：
左侧的公式按照输入顺序输出（可能不全），右侧的定理如果罗列其编号，应该是所有可能情况中字典序最小的。比如样例，其定理编号序列可能有1-2-3和1-3-2两种，尽管1-3-2是符合科学的（znfc=质能方程，nddedl=牛顿第二定律，lxqtfc=理想气体方程），但是要输出1-2-3。因为其字典序最小。
数据范围：30%数据，n,m<=600
100%的数据，n,m<=10000
p<=n+m
提示：数据保证每个公式最多对应两个定理。请注意图的存储方式。
【解题思路】
这道题实际上是我根据NOI2009第一试第一题改编的。属于那道题的加强版，在字符串处理上增加了难度。使得题目变得更加恶心。
首先是把公式和定理存储在一棵Trie树中以便后期的调用。我们给公式和定理进行编号，然后把公式作为二分图的X部，定理作为二分图的Y部，按照数据的对应关系进行构图。构图结束后，进行二分图匹配。注意，普通的二分图匹配只能保证匹配数最大，不能保证字典序。而保证字典序的方法主要有两种，一种是先采用标准的匈牙利算法求出一个原始匹配，再进行尝试调整。所谓尝试调整就是从上到下，尝试在不改变上方已调试过的匹配的情况下，将当前的X部元素匹配给更小的元素（如果本来就匹配了较小的就不用调整）。如果成功，会改变一条交错路上的匹配情况。所有的都尝试一次后就的结果就是答案。还有一种比较简单的做法是在匈牙利算法中倒叙循环X部的节点，对每个节点先尝试与较小的Y部节点匹配，再尝试较大的。这样做的合理性在于使得靠前的节点能优先匹配编号小的节点，所以字典序得到保证。
做完匹配，还需要把节点对应的字符串输出。
【代码】
program cphop;
//===========================================
const
form:array[48..90] of longint=
(
1,2,3,4,5,6,7,8,9,10, //'0'..'9'
0,0,0,11,0,0,0, //'='
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 //'A'..'Z'
);
//===========================================
var
i,j,k,l,m,n,p,q,r,t,ans:longint;
trie_form:array[0..150000,1..37] of longint;
trie_theo:array[0..200000,1..26] of longint;
form_num:array[0..150000] of longint;
theo_num:array[0..200000] of longint;
edge:array[0..10000,0..4] of longint;
formula,theo:array[0..10000] of string;
sel:array[0..10000] of boolean;
link,match:array[0..10000] of longint;
s,mid,mm:string;c:char;
//===========================================
procedure swap(var x,y:longint);
var g:longint;
begin
g:=x;x:=y;y:=g;
end;
//-------------------------------------------
function find(x:longint):boolean;
var g:longint;
begin
for g:=1 to edge[x,0] do if not sel[edge[x,g]] then
begin
sel[edge[x,g]]:=true;
if (link[edge[x,g]]=0)or(find(link[edge[x,g]])) then
begin
link[edge[x,g]]:=x;
exit(true);
end;
end;
exit(false);
end;
//-------------------------------------------
procedure main;
begin
for i:=1 to n do
begin
for j:=1 to edge[i,0]-1 do
for k:=j+1 to edge[i,0] do
if edge[i,j]>edge[i,k] then
swap(edge[i,j],edge[i,k]);
k:=1;
for j:=2 to edge[i,0] do
if edge[i,j]>edge[i,k] then
begin
inc(k);edge[i,k]:=edge[i,j];
end;
edge[i,0]:=k;
end;
ans:=0;
for i:=n downto 1 do
begin
fillchar(sel,sizeof(sel),false);
if find(i) then inc(ans);
end;
writeln(ans);
for i:=1 to m do match[link[i]]:=i;
for i:=1 to n do if match[i]>0 then
writeln(formula[i],' ',theo[match[i]]);
close(output);
end;
//-------------------------------------------
procedure add(l,r:longint);
begin
inc(edge[l,0]);
edge[l,edge[l,0]]:=r;
end;
//-------------------------------------------
function get_form(s:string):longint;
var g,t:longint;
begin
t:=0;
for g:=1 to length(s) do
t:=trie_form[t,form[ord(s[g])]];
exit(form_num[t]);
end;
//-------------------------------------------
function get_theo(s:string):longint;
var g,t:longint;
begin
t:=0;
for g:=1 to length(s) do
t:=trie_theo[t,ord(s[g])-96];
exit(theo_num[t]);
end;
//-------------------------------------------
procedure init;
begin
readln(n,m);
k:=0;p:=0;q:=0;mm:='';
while not eoln do
begin
read(c);
if c=' ' then
begin
inc(p);
form_num[k]:=p;
formula[p]:=mm;
k:=0;mm:='';
continue;
end;
mm:=mm+c;
t:=form[ord(c)];
if trie_form[k,t]>0 then
k:=trie_form[k,t] else
begin
inc(q);
trie_form[k,t]:=q;
k:=q;
end;
end;
readln;
inc(p);
form_num[k]:=p;
formula[p]:=mm;
k:=0;p:=0;q:=0;mm:='';
while not eoln do
begin
read(c);
if c=' ' then
begin
inc(p);
theo_num[k]:=p;
theo[p]:=mm;
k:=0;mm:='';
continue;
end;
mm:=mm+c;
t:=ord(c)-ord('a')+1;
if trie_theo[k,t]>0 then
k:=trie_theo[k,t] else
begin
inc(q);
trie_theo[k,t]:=q;
k:=q;
end;
end;
readln;
inc(p);
theo_num[k]:=p;
theo[p]:=mm;
readln(p);
for i:=1 to p do
begin
readln(s);
k:=pos(' ',s);
if s[1] in ['a'..'z'] then
begin
mid:=copy(s,1,k-1);
l:=get_theo(mid);
delete(s,1,k);
k:=pos(' ',s);
if k>0 then
begin
mid:=copy(s,1,k-1);
r:=get_form(mid);
delete(s,1,k);
add(r,l);
r:=get_form(s);
add(r,l);
end else
begin
r:=get_form(s);
add(r,l);
end;
end else
begin
mid:=copy(s,1,k-1);
l:=get_form(mid);
delete(s,1,k);
k:=pos(' ',s);
if k>0 then
begin
mid:=copy(s,1,k-1);
r:=get_theo(mid);
delete(s,1,k);
add(l,r);
r:=get_theo(s);
add(l,r);
end else
begin
r:=get_theo(s);
add(l,r);
end;
end;
end;
end;
//-------------------------------------------
procedure set_file;
begin
assign(input,'cphop.in');
reset(input);
assign(output,'cphop.out');
rewrite(output);
end;
//===========================================
begin
set_file;
init;
main;
end.
在NOI考挂之后，SRC希望能重演cccum神牛的传奇，于是在双哥不知情的情况下偷偷跑到了物理竞赛组学习
PhO（Physicis Olympiad）。由于离物理省赛时间不多了，加上SRC没怎么接触过物理竞赛，这其中遇到的重重困难可想而知。
物理竞赛中需要记背的公式、定理、物理常数非常之多，这对于记忆力不是很好的SRC来说是很大的挑战。虽然已经把所有的知识看过一遍，但SRC还是没有记清楚所有的这些东西。不过，有一点是肯定的，那就是SRC记住了每个公式大概是什么意思。比如有公式E=MC2，SRC会说：它的含义是动量守恒，或者是角动量守恒，或者是质能方程。而对于一个定理，比如机械能守恒定律，SRC会说：它的公式表示为C=λf，或者是Ep1+Ek1=Ep2+Ek2，或者是PV=nRT。你看，虽然SRC不能确定某些公式的具体含义或某些定理的公式，但是他会限定一个含义范围，而这个范围中一定包含了该公式或定理的正确解释。
可是，这还不够，物理竞赛中是不能答许多答案让判卷老师挑出一个正确解答的。因此SRC需要你的帮助。
他把他所记忆的公式和定理之间的对应关系告诉正在机房的你，请你帮忙编一个程序告诉他一个对应关系。这个关系应包含尽量多的公式与定理的一一对应。当然，可能有多个对应关系的公式与定理的一一对应数目是一样多且最多的，所以你只需输出字典序最小的一组对应关系即可。关于字典序最小的定义参看样例解释。
【输入格式】（cphop.in）
第一行是两个数n、m，n表示公式个数，m表示定理个数。
接下来一行有若干个单词，由空格分隔，为公式。注意，公式仅可能包含’A’..’Z’，’0’..’9’ 和’=’这37个字符。
接下来一行为若干个单词，由空格分隔，为定理。定理仅可能包含’a’..’z’这26个字符。
以上任何一个公式的长度不大于15，定理的长度不大于20。
接下来为一个数p,表示对应关系数目。
接下来p行为每行都是一个对应关系的具体描述，包括最多三个，最少两个单词，由空格分隔。假如第一个单词是一个公式，则接下来的单词表示的是一些定理，也就是SRC认为该公式的含义为该行给出的定理之一。反过来，如果第一个单词是一个定理，那么下面的单词就是公式。这个你不必验证。
【输出格式】（cphop.out）
第一行为一个数，表示你找到了多少公式与定理之间的一一对应。
接下来若干行，每行由两个单词构成，第一个单词为一个公式，第二个单词为一个定理。是对你找到的对应关系的描述。
【样例输入】
3 3
E=MC2 PV=NRT F=MA
znfc nddedl lxqtfc
3
PV=NRT nddedl lxqtfc
znfc E=MC2
F=MA nddedl lxqtfc
【样例输出】
3
E=MC2 znfc
PV=NRT nddedl
F=MA lxqtfc
解释：
左侧的公式按照输入顺序输出（可能不全），右侧的定理如果罗列其编号，应该是所有可能情况中字典序最小的。比如样例，其定理编号序列可能有1-2-3和1-3-2两种，尽管1-3-2是符合科学的（znfc=质能方程，nddedl=牛顿第二定律，lxqtfc=理想气体方程），但是要输出1-2-3。因为其字典序最小。
数据范围：30%数据，n,m<=600
100%的数据，n,m<=10000
p<=n+m
提示：数据保证每个公式最多对应两个定理。请注意图的存储方式。
【解题思路】
这道题实际上是我根据NOI2009第一试第一题改编的。属于那道题的加强版，在字符串处理上增加了难度。使得题目变得更加恶心。
首先是把公式和定理存储在一棵Trie树中以便后期的调用。我们给公式和定理进行编号，然后把公式作为二分图的X部，定理作为二分图的Y部，按照数据的对应关系进行构图。构图结束后，进行二分图匹配。注意，普通的二分图匹配只能保证匹配数最大，不能保证字典序。而保证字典序的方法主要有两种，一种是先采用标准的匈牙利算法求出一个原始匹配，再进行尝试调整。所谓尝试调整就是从上到下，尝试在不改变上方已调试过的匹配的情况下，将当前的X部元素匹配给更小的元素（如果本来就匹配了较小的就不用调整）。如果成功，会改变一条交错路上的匹配情况。所有的都尝试一次后就的结果就是答案。还有一种比较简单的做法是在匈牙利算法中倒叙循环X部的节点，对每个节点先尝试与较小的Y部节点匹配，再尝试较大的。这样做的合理性在于使得靠前的节点能优先匹配编号小的节点，所以字典序得到保证。
做完匹配，还需要把节点对应的字符串输出。
【代码】
program cphop;
//===========================================
const
form:array[48..90] of longint=
(
1,2,3,4,5,6,7,8,9,10, //'0'..'9'
0,0,0,11,0,0,0, //'='
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 //'A'..'Z'
);
//===========================================
var
i,j,k,l,m,n,p,q,r,t,ans:longint;
trie_form:array[0..150000,1..37] of longint;
trie_theo:array[0..200000,1..26] of longint;
form_num:array[0..150000] of longint;
theo_num:array[0..200000] of longint;
edge:array[0..10000,0..4] of longint;
formula,theo:array[0..10000] of string;
sel:array[0..10000] of boolean;
link,match:array[0..10000] of longint;
s,mid,mm:string;c:char;
//===========================================
procedure swap(var x,y:longint);
var g:longint;
begin
g:=x;x:=y;y:=g;
end;
//-------------------------------------------
function find(x:longint):boolean;
var g:longint;
begin
for g:=1 to edge[x,0] do if not sel[edge[x,g]] then
begin
sel[edge[x,g]]:=true;
if (link[edge[x,g]]=0)or(find(link[edge[x,g]])) then
begin
link[edge[x,g]]:=x;
exit(true);
end;
end;
exit(false);
end;
//-------------------------------------------
procedure main;
begin
for i:=1 to n do
begin
for j:=1 to edge[i,0]-1 do
for k:=j+1 to edge[i,0] do
if edge[i,j]>edge[i,k] then
swap(edge[i,j],edge[i,k]);
k:=1;
for j:=2 to edge[i,0] do
if edge[i,j]>edge[i,k] then
begin
inc(k);edge[i,k]:=edge[i,j];
end;
edge[i,0]:=k;
end;
ans:=0;
for i:=n downto 1 do
begin
fillchar(sel,sizeof(sel),false);
if find(i) then inc(ans);
end;
writeln(ans);
for i:=1 to m do match[link[i]]:=i;
for i:=1 to n do if match[i]>0 then
writeln(formula[i],' ',theo[match[i]]);
close(output);
end;
//-------------------------------------------
procedure add(l,r:longint);
begin
inc(edge[l,0]);
edge[l,edge[l,0]]:=r;
end;
//-------------------------------------------
function get_form(s:string):longint;
var g,t:longint;
begin
t:=0;
for g:=1 to length(s) do
t:=trie_form[t,form[ord(s[g])]];
exit(form_num[t]);
end;
//-------------------------------------------
function get_theo(s:string):longint;
var g,t:longint;
begin
t:=0;
for g:=1 to length(s) do
t:=trie_theo[t,ord(s[g])-96];
exit(theo_num[t]);
end;
//-------------------------------------------
procedure init;
begin
readln(n,m);
k:=0;p:=0;q:=0;mm:='';
while not eoln do
begin
read(c);
if c=' ' then
begin
inc(p);
form_num[k]:=p;
formula[p]:=mm;
k:=0;mm:='';
continue;
end;
mm:=mm+c;
t:=form[ord(c)];
if trie_form[k,t]>0 then
k:=trie_form[k,t] else
begin
inc(q);
trie_form[k,t]:=q;
k:=q;
end;
end;
readln;
inc(p);
form_num[k]:=p;
formula[p]:=mm;
k:=0;p:=0;q:=0;mm:='';
while not eoln do
begin
read(c);
if c=' ' then
begin
inc(p);
theo_num[k]:=p;
theo[p]:=mm;
k:=0;mm:='';
continue;
end;
mm:=mm+c;
t:=ord(c)-ord('a')+1;
if trie_theo[k,t]>0 then
k:=trie_theo[k,t] else
begin
inc(q);
trie_theo[k,t]:=q;
k:=q;
end;
end;
readln;
inc(p);
theo_num[k]:=p;
theo[p]:=mm;
readln(p);
for i:=1 to p do
begin
readln(s);
k:=pos(' ',s);
if s[1] in ['a'..'z'] then
begin
mid:=copy(s,1,k-1);
l:=get_theo(mid);
delete(s,1,k);
k:=pos(' ',s);
if k>0 then
begin
mid:=copy(s,1,k-1);
r:=get_form(mid);
delete(s,1,k);
add(r,l);
r:=get_form(s);
add(r,l);
end else
begin
r:=get_form(s);
add(r,l);
end;
end else
begin
mid:=copy(s,1,k-1);
l:=get_form(mid);
delete(s,1,k);
k:=pos(' ',s);
if k>0 then
begin
mid:=copy(s,1,k-1);
r:=get_theo(mid);
delete(s,1,k);
add(l,r);
r:=get_theo(s);
add(l,r);
end else
begin
r:=get_theo(s);
add(l,r);
end;
end;
end;
end;
//-------------------------------------------
procedure set_file;
begin
assign(input,'cphop.in');
reset(input);
assign(output,'cphop.out');
rewrite(output);
end;
//===========================================
begin
set_file;
init;
main;
end.