bzoj3632

心已赠人 2021-12-23 07:39 295阅读 0赞

裸的最大团，随机化大法好

多次随机出一个选择顺序然后贪心即可

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 var b:array[0..51,0..51] of boolean;
  2.  2     a:array[0..51] of longint;
  3.  3     v:array[0..51] of boolean;
  4.  4     n,m,i,j,x,y,ans:longint;
  5.  5 
  6.  6 procedure swap(var a,b:longint);
  7.  7   var c:longint;
  8.  8   begin  
  9.  9     c:=a;
  10. 10     a:=b;
  11. 11     b:=c;
  12. 12   end;
  13. 13   
  14. 14 procedure work;
  15. 15   var i,j,s:longint;
  16. 16   begin
  17. 17     s:=0;
  18. 18     fillchar(v,sizeof(v),false);
  19. 19     for i:=1 to n do
  20. 20       if not v[a[i]] then
  21. 21       begin
  22. 22         v[a[i]]:=true;
  23. 23         for j:=i+1 to n do
  24. 24           if not b[a[i],a[j]] then v[a[j]]:=true;
  25. 25         inc(s);
  26. 26       end;
  27. 27     if ans<s then ans:=s;
  28. 28   end;
  29. 29 
  30. 30 begin
  31. 31   readln(n);
  32. 32   while not eof do 
  33. 33   begin
  34. 34     readln(x,y);
  35. 35     b[x,y]:=true;
  36. 36     b[y,x]:=true;
  37. 37   end;
  38. 38   for i:=1 to n do
  39. 39     a[i]:=i;
  40. 40   work;
  41. 41   for i:=1 to 15000 do
  42. 42   begin
  43. 43     for j:=2 to n do
  44. 44       swap(a[j],a[trunc(random*j)+1]);
  45. 45     work;
  46. 46   end;
  47. 47   writeln(ans);
  48. 48 end.

转载于:https://www.cnblogs.com/phile/p/4609674.html

发表评论

表情：
评论列表 （有 0 条评论，295人围观）

还没有评论，来说两句吧...

相关阅读

    相关 BZOJ2938

    BZOJ2938-病毒 题意： > 二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们...

    偏执的太偏执、偏执的太偏执、/ 0 赞/ 182 阅读

    相关 bzoj3632

    裸的最大团，随机化大法好 多次随机出一个选择顺序然后贪心即可 ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

    心已赠人心已赠人/ 0 赞/ 296 阅读

    相关 bzoj4042

    比较好的树形dp，涉及到树上路径的题目，我们往往考虑对路径分类 当我们考虑以x为根的子树，有这样几类路径 1. 起点终点都在子树内 2. 一个点延伸到子树外 对于要选择

    ゝ一世哀愁。ゝ一世哀愁。/ 0 赞/ 245 阅读

    相关 bzoj 1834

    网络流的模板题 首先第一问我们直接用dinic搞就行了，费用直接存为0（时间上界非常松，这道题是能过），然后第二问我们只需要在第一问 的残余网络上加一个源点，源点指向1号点

    灰太狼灰太狼/ 0 赞/ 343 阅读

    相关 【BZOJ2019】nim

    著名游戏设计师vfleaking，最近迷上了Nim。普通的Nim游戏为：两个人进行游戏，N堆石子，每回合可以取其中某一堆的任意多个，可以取完，但不可以不取。谁不能取谁输。...

    你的名字你的名字/ 0 赞/ 569 阅读

    相关 bzoj4407

    以前写过一次线性筛 发现不是很理解 写了个欧拉筛的 t了 其实每次推式子，都会先推出一组的

    红太狼红太狼/ 0 赞/ 533 阅读