德州网站建设优化,网站栏目页如何做,企业网站设计建设服务,南昌网站seo厂家问题 宇宙时间公元 5.55 亿年#xff0c;由于某种原因两大联盟展开了激战#xff08;maxingc 联盟采用了微子技术#xff09;#xff1a; 邪恶的 maxingc 联盟采集好了微子能#xff0c;就要运输。Maxingc 联盟的领袖 xc 此时才发现#xff0c;自己的军事基地中由微子发射…问题 宇宙时间公元 5.55 亿年由于某种原因两大联盟展开了激战maxingc 联盟采用了微子技术 邪恶的 maxingc 联盟采集好了微子能就要运输。Maxingc 联盟的领袖 xc 此时才发现自己的军事基地中由微子发射器组成的微子能量网存在很大的问题于是他决定修改。 之前TT 为了整齐把军事基地建成了矩形而且如果两个微子发射器的连线平行于军事基地的一边这两个微子发射器之间就一定有微子能量传输线相连。 (*注比如有 3 个微子发射器A11、B13、C22那么 A 和 B 之间有微子能量传输线相连A 和 B 不能传输到 C。*) 但是在微子能运输过程中发现常常不能从一个微子发射器运抵另一个微子发射器。 为了可以从任何一个微子传输器能运抵其它任意一个微子传输器而且能和原来的微子能量网同样整齐TT 决定遵循原来的规则调动他的百万农奴新修建一些微子能量传输线和微子发射器。由于微子发射器的造价比微子传输线高得多所以 TT 决定忽略微子能量传输线的成本。 但是 TT 又不想花费不必要的钱所以找到你为他计算最少需要建多少个微子发射器。 输入格式 Input Format 第一行三个正整数 n、m、p。(2n,m100000表示军事基地的两边长2p200000表示微子 发射器的个数。) 接下来 p行每行两个正整数数 Xi、 Yi(1Xin 1Yim)代表每个微子发射器在军事基地的位置。可能会由于疏漏有些微子发射器重复 输出格式 Output Format 样例: 输入5 6 6 1 1 2 2 2 4 3 3 5 1 5 5 输出 2 只有一行为最少修建微子发射器的数量。 样例的一种方案 #..... |#-#.. |.#.. |.|... #--#. #表示原有微子发射器-、|表示微子能量传输线表示兴建的微子发射器。所以至少兴建 2 个微子发射器。 分析 我们先这样考虑如果对所有已知的节点进行染色的话能染成同一种颜色的节点一定在同一个强连通分量中(内部连同)那么需要兴建的节点数就等于强连通分量数减一 我们来证明这个结论对于任意一个节点它可以照顾到一行一列上的所有节点。也就是说一个节点最多可以连接到4个强连通分量。如果一个兴建的节点只连接一个强连通分量那么这个节点是毫无用处的。如果一个节点连接3个强连同分量那么这3个强连通分量必有两个已经在一个强连通分量中。连接4个同理。只有当一个节点连接两个强连通分量时才能让这两个原先不连通的分量相互连同。 这就类似于最小生成树将兴建的节点看成边原有的强连通分量看做节点那么n个节点连成一颗生成树必然需要n-1个节点。 下面的问题就是如何染色。 如果用floodfill会很复杂而且显然会超时。我们要考虑更加优秀的的算法。我们现在需要将在一个强连通分量中的原节点赋予同一个标识并查集 再加一个标记数组nm 表示某行或某列上是否有节点。每读入一个节点我们就将其所在的行和列和并在一个集合中。这样就将一个强连同分量中的所有行和列合并在了同一个集合中。 最后只需要枚举每行列如果该行列被标记过在某个强连通分量中那么找到它的根节点累计总数并且标记当前强连通分量被访问过应用并查集压缩路径后在同一个集合中的元素的祖先相同只需标记其祖先即可。 View Code program liukeke;var f:array[1..400000] of longint; v:array[1..400000] of boolean; i,n,m,p,x,y,temp1,temp2,ans:longint;function find(x:longint):longint;beginif f[x]x then exit(x); f[x]:find(f[x]); exit(f[x]);end;begin assign(input,wei.in);reset(input); assign(output,wei.out);rewrite(output); readln(n,m,p);for i:1 to nm do f[i]:i;for i:1 to p dobegin readln(x,y); temp1:find(x); temp2:find(yn);if temp1temp2 then f[temp1]:temp2; v[x]:true; v[yn]:true;end;for i:1 to nm doif v[i] then begin temp1:find(i);if v[temp1] thenbegin inc(ans); v[temp1]:false;end;end; writeln(ans-1); close(input); close(output);end. 反思 要先对题目分析抽象其模型再选取合适的数据结构解决问题并查集应用不多但都很巧妙可用来判断逻辑关系和集合关系转载于:https://www.cnblogs.com/liukeke/archive/2011/06/12/2078972.html
