首页 > 代码库 > 浮云洲之战

浮云洲之战

2024-07-13 02:46:07   210人阅读

浮云洲之战
(seawar.pas/c/cpp)
题目描述
浮云洲是东海岸畔一个风景如画的小岛，信仰海神的渔民们在此世代捕鱼为生。浮云洲
的领导者被称为司卜，掌管岛上的大事，鲁明星就是司卜家的女儿。与浮云洲的居民一样，
鲁明星天生有着对大自然无比的热爱和对小动物的怜悯，但与大家不同的是，小小的她早已
踏遍各地河山，有着面对危险时勇敢果断的号召力和战斗精神。在游历的过程中，鲁明星认
识了精通兵法、武艺超群的豪侠管毅。意趣相投的两人结伴而行，共同来到了浮云洲。此时
恰逢海贼入侵浮云洲，面对软弱的岛民们，鲁明星坚决担负起了组织击退入侵者的重任。
浮云洲的村庄之间通过单向道路连接，构成一个有向无环图。如果在某个村庄安排了守
卫，那么这个守卫可以沿着某一条从这个村庄出发的路径走下去，在路径上的所有道路上安
放战斗设施。现在鲁明星想知道，要想使所有的道路都被安放战斗设施，最少需要多少名守
卫？
输入格式
第一行一个整数 n，表示浮云洲里村庄的个数。
接下来 n 行，每行的第一个数是一个整数，其中第 i+1 行的数是 di，表示从村庄 i 出发
有 di 条道路。每行紧接着会有 di 个整数，表示这些道路到达的村庄。
输出格式
一个整数 ans，表示最少需要的守卫人数。
样例输入
8
1 3
1 7
2 4 5
1 8
1 8
0
2 6 5
0
样例输出
4
数据范围与约定
对于 30% 的数据，满足 2<=n<=10。
对于 100% 的数据，满足 2<=n<=100，0<=di<n，没有重边和自环。

题解：

当时对网络流还不熟悉，后来一反应，这不是一个裸的有下界最小流吗，可惜我当时想到也不会求……

具体方法见我下一篇博文

代码：

  1 const inf=maxlongint;  2 type node=record  3      from,go,next,v:longint;  4      end;  5 var  tot,i,j,n,m,maxflow,l,r,s,t,x,y,ans,ss,tt:longint;  6      h,head,q,cur,indeg,outdeg:array[0..500] of longint;  7      e:array[0..50000] of node;  8      function min(x,y:longint):longint;  9       begin 10       if x<y then exit(x) else exit(y); 11       end; 12 procedure ins(x,y,z:longint); 13  begin 14  inc(tot); 15  e[tot].from:=x;e[tot].go:=y;e[tot].v:=z;e[tot].next:=head[x];head[x]:=tot; 16  end; 17 procedure insert(x,y,z:longint); 18  begin 19  ins(x,y,z);ins(y,x,0); 20  end; 21 function bfs:boolean; 22  var i,x,y:longint; 23  begin 24  fillchar(h,sizeof(h),0); 25  l:=0;r:=1;q[1]:=s;h[s]:=1; 26  while l<r do 27   begin 28   inc(l); 29   x:=q[l]; 30   i:=head[x]; 31   while i<>0 do 32    begin 33    y:=e[i].go; 34    if (e[i].v<>0) and (h[y]=0) then 35     begin 36      h[y]:=h[x]+1; 37      inc(r);q[r]:=y; 38     end; 39    i:=e[i].next; 40    end; 41   end; 42  exit (h[t]<>0); 43  end; 44 function dfs(x,f:longint):longint; 45  var i,y,used,tmp:longint; 46  begin 47  if x=t then exit(f); 48  used:=0; 49  i:=cur[x]; 50  while i<>0 do 51   begin 52   y:=e[i].go; 53   if (h[y]=h[x]+1) and (e[i].v<>0) then 54    begin 55    tmp:=dfs(y,min(e[i].v,f-used)); 56    dec(e[i].v,tmp);if e[i].v<>0 then cur[x]:=i; 57    inc(e[i xor 1].v,tmp); 58    inc(used,tmp); 59    if used=f then exit(f); 60    end; 61   i:=e[i].next; 62   end; 63  if used=0 then h[x]:=-1; 64  exit(used); 65  end; 66 procedure dinic; 67  begin 68  while bfs do 69   begin 70   for i:=0 to n+3 do cur[i]:=head[i]; 71   inc(maxflow,dfs(s,inf)); 72   end; 73  end; 74 procedure init; 75  begin 76  tot:=1; 77  readln(n); 78  s:=0;t:=n+1; 79  ss:=n+2;tt:=n+3; 80  for i:=1 to n do 81   begin 82   read(outdeg[i]); 83   for j:=1 to outdeg[i] do 84    begin 85     read(x); 86     inc(indeg[x]); 87     insert(i,x,inf); 88     insert(i,tt,1); 89     insert(ss,x,1); 90    end; 91   end; 92  for i:=1 to n do 93   begin 94    if indeg[i]=0 then insert(s,i,inf); 95    if outdeg[i]=0 then insert(i,t,inf); 96   end; 97  insert(t,s,inf); 98  end; 99 procedure main;100  begin101  s:=ss;t:=tt;102  maxflow:=0;103  dinic;104  ans:=e[tot].v;105  e[tot].v:=0;e[tot xor 1].v:=0;106  s:=n+1;t:=0;107  maxflow:=0;108  dinic;109  writeln(ans-maxflow);110  end;111 begin112  assign(input,‘input.txt‘);assign(output,‘output.txt‘);113  reset(input);rewrite(output);114  init;115  main;116  close(input);close(output);117 end.
View Code


联系
我们