2012福建省信息学奥林匹克CCF-NOIP夏令营第六天训练(附解题思路及参考程序).doc

(完整版)2012福建省信息学奥林匹克CCF NOIP夏令营第六天训练(附解题思路及参考程序)

2012福建省信息学奥林匹克CCF NOIP夏令营第六天训练
（附解题思路及参考程序）

问题名称
文件名
输入文件
输出文件
时限
分值
地震逃生
earthquake
earthquake。in
earthquake。out
1s
100
追查坏牛奶
milk
milk。in
milk。out
1s
100
奶牛的电信
telecow
telecow.in
telecow。out
1s
100
电车
tram
tram.in
tram.out
1s
100
排序
sort
sort。in
sort.out
1s
100
内存限制均为256M
（前3题为网络流练习题,选做。今天下午主要练习第4，，第5题,第一题可以用来尝试编写上午学的网络流算法。)

*地震逃生(earthquake)

【问题描述】
汶川地震发生时，四川*＊中学正在上课，一看地震发生，老师们立刻带领x名学生逃跑，整个学校可以抽象地看成一个有向图，图中有n个点,m条边。1号点为教室,n号点为安全地带,每条边都只能容纳一定量的学生，超过楼就要倒塌，由于人数太多，校长决定让同学们分成几批逃生,只有第一批学生全部逃生完毕后，第二批学生才能从1号点出发逃生，现在请你帮校长算算,每批最多能运出多少个学生，x名学生分几批才能运完。
【输入文件】
第一行3个整数n,m，x(x<2^31，n<=200,m<=2000）；以下m行,每行三个整数a，b，c（a1,a〈〉b，0描述一条边，分别代表从a点到b点有一条边，且可容纳c名学生。
【输出文件】
两个整数，分别表示每批最多能运出多少个学生，x名学生分几批才能运完。如果无法到达目的地(n号点）则输出“Orz Ni Jinan Saint Cow!”
【样例输入】
6 7 7
1 2 1
1 4 2
2 3 1
4 5 1
4 3 1
3 6 2
5 6 1
【样例输出】
3 3
【注释】
比如有图

1 2 100
2 3 1

100个学生先冲到2号点，然后1个1个慢慢沿2—3边走过去
18神牛规定这样是不可以的……
也就是说,每批学生必须同时从起点出发，并且同时到达终点
*追查坏牛奶(milk）

【问题描述】
你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶.很不幸，你发现这件事的时候,有三聚氰胺的牛奶已经进入了送货网。这个送货网很大,而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成,每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失.你的任务是,在保证坏牛奶不送到零售商的前提下,制定出停止卡车运输的方案，使损失最小。
【输入文件】
第一行: 两个整数N(2<=N<=32)、M（0〈=M〈=1000）， N表示仓库的数目,M表示运输卡车的数量。仓库1代 表发货工厂，仓库N代表有三聚氰胺的牛奶要发往的零售商。 第2。.M+1行: 每行3个整数Si，Ei,Ci.其中Si,Ei表示这 辆卡车的出发仓库，目的仓库。Ci（0 〈= C i <= 2，000,000） 表示让这辆卡车停止运输的损失。
【输出文件】
两个整数C、T：C表示最小的损失，T表示在损失最小的前提下,最少要停止的卡车数。
【样例输入】
4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80
【样例输出】
60 1
*奶牛的电信(telecow）

【问题描述】
农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由c台电脑组成的序列a1,a2,..。，a（c），且a1与a2相连，a2与a3相连，等等，那么电脑a1和a(c）就可以互发电邮。

很不幸，有时候奶牛会不小心踩到电脑上,农夫约翰的车也可能碾过电脑,这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了，于是与这台电脑相关的连接也就不可用了.

有两头奶牛就想：如果我们两个不能互发电邮，至少需要坏掉多少台电脑呢？请编写一个程序为她们计算这个最小值.

以如下网络为例：

　　　　　　 1＊
　　　　　　 /
　　　　　　 3 - 2＊

这张图画的是有2条连接的3台电脑。我们想要在电脑1和2之间传送信息。电脑1与3、2与3直接连通。如果电脑3坏了，电脑1与2便不能互发信息了.
【输入文件】
第一行 四个由空格分隔的整数:N,M，c1,c2。N是电脑总数(1<=N<=100)，电脑由1到N编号。M是电脑之间连接的总数（1〈=M<=600）。最后的两个整数c1和c2是上述两头奶牛使用的电脑编号。连接没有重复且均为双向的（即如果c1与c2相连，那么c2与c1也相连）。两台电脑之间至多有一条连接.电脑c1和c2不会直接相连。
第2到M+1行 接下来的M行中，每行包含两台直接相连的电脑的编号。
【输出文件】
一个整数表示使电脑c1和c2不能互相通信需要坏掉的电脑数目的最小值。
【样例输入】
3 2 1 2
1 3
2 3
【样例输出】
1
电车（tram)
【问题描述】
在一个神奇的小镇上有着一个特别的电车网络，它由一些路口和轨道组成，每个路口都连接着若干个轨道，每个轨道都通向一个路口(不排除有的观光轨道转一圈后返回路口的可能).在每个路口，都有一个开关决定着出去的轨道,每个开关都有一个默认的状态，每辆电车行驶到路口之后，只能从开关所指向的轨道出去，如果电车司机想走另一个轨道，他就必须下车切换开关的状态。
为了行驶向目标地点,电车司机不得不经常下车来切换开关，于是，他们想请你写一个程序,计算一辆从路口A到路口B最少需要下车切换几次开关。
【输入文件】
第一行有3个整数2〈=N〈=100，1〈=A，B<=N,分别表示路口的数量,和电车的起点，终点。
接下来有N行，每行的开头有一个数字Ki（0<=Ki<=N-1)，表示这个路口与Ki条轨道相连，接下来有Ki个数字表示每条轨道所通向的路口，开关默认指向第一个数字表示的轨道。
【输出文件】
输出文件只有一个数字，表示从A到B所需的最少的切换开关次数，若无法从A前往B,输出—1.
【样例输入】
3 2 1
2 2 3
2 3 1
2 1 2
【样例输出】
0
排序（sort)
【问题描述】
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列A，B,C,D 表示A〈B，B<C，C〈D。在这道题中，我们将给你一系列形如A〈B的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。
【输入文件】
第一行有两个整数n,m，n表示需要排序的元素数量,2<=n〈=26，第1到n个元素将用大写的A,B,C，D..。.表示。m表示将给出的形如A<B的关系的数量.
接下来有m行，每行有3个字符,分别为一个大写字母，一个<符号，一个大写字母，表示两个元素之间的关系。
【输出文件】
若根据前x个关系即可确定这n个元素的顺序yyy..y（如ABC），输出
Sorted sequence determined after xxx relations: yyy。.。y。
若根据前x个关系即发现存在矛盾(如A〈B,B〈C，C<A），输出
Inconsistency found after 2 relations.
若根据这m个关系无法确定这n个元素的顺序，输出
Sorted sequence cannot be determined.
(提示：确定n个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）
【样例输入】
1：
4 6
A〈B
A<C
B〈C
C<D
B<D
A〈B

2：
3 2
A〈B
B〈A

3:
26 1
A<Z
【样例输出】
1:
Sorted sequence determined after 4 relations： ABCD.
2：
Inconsistency found after 2 relations.
3:
Sorted sequence cannot be determined.
地震逃生：基础的求最大流
题目大意：
给出n个点，m条边，求从点1到点n的最大流。
解题思路:
使用任意一种网络流算法皆可
参考程序：
program earthquake；

var
n， m, stu, u, v, ans， add : longint；
c : array[1。.202,1。.202]of longint;
cover ： array[1..202]of boolean；

function min（ a， b : longint ) ： longint；
begin
if a 〈 b then min ：= a else min ：= b；
end;

function aug( x, low ： longint ) : longint;
var
i， d ： longint；
begin
aug := 0；
if cover［x] then exit;
cover[x] := true；
if x = n then begin aug := low; exit； end；
for i ：= 1 to n do
if c［x]［i］ > 0 then begin
d := aug( i, min( low, c［x］［i］ ） ）;
if d > 0 then begin
dec（ c[x］［i］, d ）;
inc（ c［i］[x], d )；
aug := d; exit;
end;
end;
end；

begin
assign( input, ’earthquake.in’ )； reset( input ）；
assign（ output， 'earthquake.out’ )； rewrite( output )；
readln( n, m, stu ）;
fillchar( c, sizeof（c)， 0 );
while m〉0 do begin
dec（ m ); readln（ u， v, ans ）； inc（ c[u］［v], ans ）；
end;
ans := 0;
repeat
for m := 1 to n do cover[m] := false；
add ：= aug( 1， maxlongint ）；
inc（ ans， add ）;
until add = 0；
if ans=0 then writeln( ’Orz Ni Jinan Saint Cow！’ )
else writeln（ ans， ’ ’， stu div ans + ord（ stu mod ans 〈〉 0 ) ）；
close（input）；
close(output)；
end.
追查坏牛奶：求最小割，对容量的修改
题目大意:
有n个点，m条边,删除每条边都有一定的损失，要使得点1与点n不再连通，求最小损失和损失最小的前提下最少需要删多少条边。
解题思路:
题目的本质是求最小割，最小割可通过最大流求得。
先考虑如何求最小损失?
将删除边的损失作为该边的容量,则图的最小割就是最小损失。
如何做到损失最小的前提下删边最小?
解题思路：
简单的想法：首先，让损失最小,在损失最小的方案中，求删边最少的最小割方案。比如，先求出最小损失为8，在最小损失为8的方案中，比起删3条边的优先选择删2条边的。
如何实现呢?
首先，我们注意到，如果将每条边的容量变为原先的1000倍,再把结果整除1000，最小损失的结果是不变的。
进而，我们可以注意到，对于一个有500个边的图，在容量扩大1000倍之后，就算将每条边的容量+1,结果也是不变的，因为新增的流量在整除后将忽略不计。
解题思路：
于是，我们可以实现先比较损失再比较删边数的功能了。
以最多500个边的图为例,将容量为w的边的容量变为1000＊w+1，结果会怎样呢？
首先,新图的最小割整除1000后就等于原先的最小割.
其次,对于原先容量相等的割，现在边数最小的才是最小割，只要将新图的最小割Mod 1000就可以得到最小割的边数了.
这道题最多有1000条边，所以将容量*1050+1作为新图的容量即可求解.
参考程序：
｛
ID：asiapea1
PROB:milk6
LANG：PASCAL
｝
const

fin='milk.in'；

fout='milk。out'；

type

node=record

s,t,c，num：longint；

end；

var

tempmap，map:array［1..32,1.。32］of longint;

vex：array［1。。10000]of node；

put:array［1。。10000］of longint；

n，e:longint;

procedure qsort（s，t：longint);

var

i,j:longint;

x:node;

begin

i:=s；j:=t;x：=vex［i］；

while i<j do

begin

while （i<j）and（vex[j]。c〈x.c) do dec(j);

vex［i］:=vex[j］;

if i<j then inc（i）；

while （i〈j)and（vex［i］。c〉x。c） do inc（i）；

vex[j]：=vex[i］;

if i〈j then dec（j);

end；

vex［i］：=x;

if s〈i-1 then qsort(s，i—1）;

if i+1〈t then qsort(i+1,t）；

end；

procedure init;

var

i，v1，v2,f：longint；

begin

assign(input,fin）；assign(output,fout);

reset(input）；rewrite（output）；

readln（n,e)；

for i：=1 to e do

begin

readln(v1,v2，f）；

inc(map［v1,v2]，f)；

vex［i］。s:=v1;vex［i］。t：=v2;vex[i］.c：=f;vex［i].num：=i；

end;

qsort(1，e）;

end;

function maxstream:longint；

var

f，c：longint;

procedure findstream;

var

flag：array[1。.32］of boolean;

have，pr：array［1..32]of longint；

mi，i，max：longint;

begin

fillchar(flag，sizeof（flag）,false);

fillchar（have,sizeof(have）,0）;

have［1]：=2000000000;pr[1]：=0；

while true do

begin

max：=0;mi：=-1；

for i:=1 to n do

if (not flag［i］）and(have[i］>max) then

begin max:=have［i］；mi：=i；end；

if mi=—1 then exit;

if mi=n then break;

flag[mi］:=true；

for i:=1 to n do

if (not flag［i]）and（map［mi，i］〉=have[i］)and（max〉=have［i]） then

begin

have[i］：=map［mi,i]；

if have[i]〉max then have[i］:=max；

pr[i]：=mi;

end;

end；

f:=have［n];i:=n；

while pr［i]〈>0 do

begin

dec（map［pr［i］，i］,f);

inc(map［i,pr[i］］,f)；

i:=pr［i］;

end;

end；

begin

f：=0；findstream;c:=0;

while f<>0 do begin inc(c,f）；f:=0；findstream;end；

maxstream:=c;

end;

procedure calc；

var

temp,f,i，total，j：longint；

begin

tempmap:=map；total:=0;

f:=maxstream;write（f,’ ’)；

for i：=1 to e do

if map［vex[i]。s,vex［i］.t］=0 then

begin

temp：=f；dec(tempmap[vex［i］。s,vex［i]。t]，vex[i]。c）;map：=tempmap；

f:=maxstream；

if temp=f+vex［i].c then

begin

inc（total)；

put[total]：=vex［i].num；

if f=0 then break；

end

else inc（tempmap［vex[i］。s,vex[i].t］，vex[i］。c）;

end;

writeln(total）;

for i:=1 to total do

begin

for j:=i+1 to total do

if put［i］>put[j］ then

begin temp:=put[i］;put［i］：=put[j]；put［j］：=temp;end；

//writeln（put［i］）；

end；

close（input);close（output)；

end；

begin

init;

calc；

end。
奶牛的电信：网络流构图
题目大意：
有N个点，M条边，问最小删除多少个点才能使得点c1与点c2之间不再连通.
解题思路：
上一题中，我们求了如何删除最少的边，这题我们需要求的是删除最少的点。
所以只要把点拆成边就可以了。
构图:
设c1为源，c2为汇
我们将其余每个点u拆为两个点u1，u2，并连接〈u1，u2>,双方向容量为1
对于原图中的每条无向边<u，v>拆为两条有向边,一条是u2到v1，一条是v2到u1，容量为正无穷
新图的最小割则为所求得最少删点数目
{
ID:asiapea1
PROB:telecow
LANG:PASCAL
}
var a,d：array[1..200,0.。200]of longint;
c2，c，cbak：array［1。。200,1.。200]of longint；
b,bb:array[1.。100]of boolean;
cut，ans,q，p:array［1。。200］of longint;
maxflow，p1，p2,x,y，n,m，s，t,s2，t1，i:longint；

procedure init;
begin
assign(input,’telecow.in'）；reset(input)；
read(n,m,s，t）；
s2:=s*2;
t1:=t*2—1;
for i：=1 to m do
begin
read（x,y)；
inc（d［x，0］）;
d[x，d[x，0］]：=y;
inc（d［y，0]）；
d[y，d［y，0］］:=x；

inc（a［x*2，0］)；
a[x*2,a［x＊2，0］］：=y*2-1;
c［x*2，y*2—1]：=999999999；
inc(a［y*2-1,0]);
a[y＊2—1,a[y＊2-1，0］]：=x*2；
c[y＊2-1，x＊2]：=0；

inc（a[y＊2,0])；
a[y*2,a［y*2，0]]:=x＊2—1;
c［y＊2,x*2—1］：=999999999;
inc(a［x＊2-1,0］）；
a［x＊2-1,a[x＊2—1，0］］:=y＊2；
c[x*2-1，y*2］：=0；
end；

for i：=1 to n do
begin
inc（a[i*2—1，0］);
a［i*2—1，a[i＊2-1，0］］:=i*2；
c[i＊2-1，i*2]：=1;
inc(a［i＊2,0]）；
a［i＊2,a[i*2，0］］:=i＊2—1;
c[i*2,i*2-1]:=0;
end;
cbak:=c;
end；

function find：boolean;
var j：longint;
begin
fillchar（p,sizeof(p）,255）；
p1:=1;p2：=1;
q[1]:=s2； p[s2］：=0;
repeat
for j：=1 to a［q[p1],0] do
if (p[a[q［p1］，j]]〈0)and (c[q［p1]，a[q［p1]，j］]〉0)
then begin
inc（p2）;
q[p2］:=a[q[p1］，j]；
p［q［p2]］：=q［p1］;
if q[p2]=t1 then exit(true);
end;
inc（p1);
until p1〉p2;
exit(false)；
end；

function flow:longint；
var i,f:longint;
begin
f：=0；
repeat
if find then begin
i：=t1；
inc(f)；
while p［i]<〉0 do
begin
dec(c[p[i],i]）；
inc（c[i,p[i］])；
i：=p[i];
end；
end
else break;
until false;
exit（f);
end;

procedure docut；
begin
maxflow:=flow;
c2:=c；
x:=0;
for i:=1 to n do
if （i<>s) and (i<>t) and （c[i＊2—1，i*2]=0）
then begin
c：=cbak；
c［i＊2-1，i＊2]:=0;
if maxflow=flow+1 then begin
inc（x);
cut[x］:=i;
end；
end;
end;

procedure out;
begin
assign（output,’telecow.out'）；rewrite（output)；
writeln（maxflow);
｛ for i:=1 to maxflow-1 do
write(ans［i］,' ’）;
writeln（ans[maxflow］）;}
close(output);
halt;
end；

function ok(i：longint)：boolean;
var j:longint;
begin
if i=t then exit（true)；
bb［i］：=false;
for j:=1 to d［i，0］ do
if b[d［i，j］] and bb[d［i，j]］ and ok(d［i,j］）
then exit（true);
exit（false);
end;

procedure dfs(i，last：longint)；
var j:longint;
begin
if i=maxflow+1 then begin
fillchar(bb，sizeof(bb)，true）；
if not ok（s） then out；
exit；
end；
for j:=last+1 to x do
begin
ans［i]：=cut[j］；
b［cut[j］]:=false；
dfs(i+1,j）；
b［cut［j]]：=true;
end;
end;

begin
init；
docut；
fillchar（b,sizeof(b),true）;
dfs(1,0);
end。
电车
题目大意：
有N个点，每个点有若干条从该点出发的边，走其中一条特定的边是不需要费用的，走其他边需要1的费用来切换开关状态，求从点A到点B的最小费用。
解题思路:
对于从路口i出发前往路口j的一条轨道，若无需切换开关，则w[i][j]=0,否则w［i]［j]=1
使用单源最短路算法求解( dijkstra或spfa）
参考程序：
＃include <iostream>
using namespace std；

const int MAX = 110;
const int INF = 0x3f3f3f3f；
int map[MAX］[MAX];
bool vis[MAX］;
int dis[MAX］;
int n, a, b;

void dijkstra(int s, int e）
{
int i, j；
int min， loc；

// 初始化从s开始的最短路
for (i=1； i<=n； ++i）
{
dis［i] = map［s]［i］;
｝
dis［s］ = 0；
vis［s] = true；
for （i=1； i〈n; ++i)
｛
min = INF；
loc = -1;
// 寻找从s出发的最短路
for （j=1; j<=n； ++j)
{
if （!vis［j] && dis[j]<min）
{
loc = j;
min = dis［j]；
}
}
if （loc == -1）
{
continue；
｝
vis[loc] = true;
//更新从s出发的最短路
for （j=1; j〈=n; ++j)
{
if （！vis［j] && dis［j］>dis［loc］+map［loc]［j］）
{
dis［j] = dis[loc］ + map［loc]［j];
｝
}
}
（dis[e］ == INF）？ cout << "-1" << endl : cout <〈 dis[e] 〈< endl;
｝

int main（)
｛
freopen（”tram。in"，"r"，stdin);
freopen(”tram.out","w",stdout)；
int k, t；
memset(vis， false， sizeof（vis)）;
memset(map， 0x3f, sizeof（map)）;
memset(dis, 0x3f， sizeof（dis））;
scanf（”％d%d％d", &n, &a, &b);
for （int i=1; i〈=n; ++i)
{
scanf("％d”， ＆k）；
for (int j=1； j<=k； ++j)
{
scanf（"％d”， ＆t）；
（j == 1)？ map［i]［t］ = 0 ： map［i］[t］ = 1；
｝
}
dijkstra(a， b）;
return 0；
}
排序
题目大意：
有n个元素，给出m条形如X<Y的关系，求需要前多少个关系才能确定数列的顺序或发现矛盾。
解题思路：
将每个元素作为一个点
每个关系X<Y对应一条X到Y的边
使用拓扑排序判断当前图是否存在确定的顺序
若存在环，则存在矛盾
最多需进行m次拓扑排序
参考程序：
＃include 〈iostream〉
#include 〈cstdio〉
＃include <cstdlib>
＃include <cstring>
＃include 〈cmath〉
using namespace std；
＃define FOR（i，a,b） for(int i=a；i<=b;i++)
＃define MST(a,b) memset（a，b,sizeof(a))
＃define MAXN 30
#define MAXM 1000
int n，m，ue［MAXM],ve[MAXM］,b[MAXM］；
int tot,first[MAXN］，next［MAXM];
void add(int u,int v）
{
ue[++tot]=u；ve[tot］=v；
next［tot］=first[u]；first[u]=tot;
｝

void init（)
｛
MST（first,0)；
char a,b;
tot=0；
FOR(i，1，m）
{
scanf(”％c〈%c\n"，＆a，&b);
int u=a-'A'+1,v=b—'A’+1;
add（u,v）;
}
｝
int d0[MAXN］，d［MAXN]；
int q[MAXN］,l，r；
int tryt(）//—1失败0成功1唯一
｛
int l=1,r=0；
FOR（i,1,n） d[i］=d0[i]；
int qd=1；
FOR(i，1,n)if (d[i］==0)q［++r]=i；
while （l<=r)
｛
if (l〈r) qd=0;
int u=q[l++]；
for(int p=first［u];p