1. 牧场装饰{bronze题3}

【问题描述】

农民约翰有N（1<= N<=50,000）牧场，分别编号为1... N。牧场由M（1<= M<=100,000）条双向道路连接。道路i连接两个不同的牧场牧场A_i（1<= A_I<= N）和牧场B_i（1<= B_i<= N）。同一对牧场之间可能有多条道路连接。

现对每个牧场摆放一块标有大写字母”F”或者”J”的广告牌进行装饰。两个有道路相连的牧场，必须摆放不同字母的广告牌。

“F”字母广告牌的价格要高于”J”字母的广告牌，所以约翰想最大化地使用”J”字母广告牌，请输出这个最大的数目，如果没有可行的摆放方案，则输出”-1”。

【文件输入】

第一行为两个整数N和M。

接下来2..M行，每行两个整数，描述M条双向道路。

【文件输出】

   输出共一行，一个整数，表示”J”字母广告牌的最大数目，无解则输出”-1”。

【输入样例1】

4 4

1 2

2 3

3 4

4 1

【输出样例1】

2

【样例1说明】

牧场1和3，或者牧场2和4使用”J”字母广告牌。

刚看到题目就觉得和某年NOIP的关押罪犯非常的相似。

果然思路是差不多的……

就是用并查集把一条边的两个端点放到不同的两个集合中，即放到另一端点的“敌对集合”中去。

最后的统计需要特殊处理一下，因为不一定只剩下两个互相敌对的集合。有些集合之间可能是毫无关系的。

所以在两个互相敌对的集合中，应该取人数多的那个集合的人数加入答案中去。

如果有的点和其他端点没有任何关系，那么也需要把它加入答案中去。

var hate,father,final:array[0..50000] of longint;
 a,b,tot:array[0..100000] of longint;
 use:array[0..50000] of boolean;
  kk,ans1,ans2,i,t1,t2,x,j,n,m,k1,k2:longint;

function getfather(k:longint):longint;
var tip:longint;
begin
 if father[k]=k then exit(k);
 tip:=father[k];
 father[k]:=getfather(tip);
 getfather:=father[k];
end;

procedure qsort(aa,bb:longint);
var i,j,x,temp:longint;
begin
i:=aa;
j:=bb;
x:=final[(i+j) div 2];
repeat
 while final[i]<x do inc(i);
 while final[j]>x do dec(j);
 if i<=j then
  begin
  temp:=final[i];
  final[i]:=final[j];
  final[j]:=temp;
  inc(i);
  dec(j);
  end;
until i>j;
if i<bb then qsort(i,bb);
if aa<j then qsort(aa,j);
end;

begin
//assign(input,‘bronze.in‘);
//assign(output,‘bronze.out‘);
//reset(input);
//rewrite(output);
readln(n,m);
for i:=1 to n do father[i]:=i;
for i:=1 to m do
  readln(a[i],b[i]);
for i:=1 to m do
 begin
  t1:=getfather(a[i]);
  t2:=getfather(b[i]);
  if t1=t2 then
   begin
    writeln(‘-1‘);
    //close(input);
    //close(output);
    halt;
   end
  else
   begin
    if hate[t1]=0 then hate[t1]:=t2;
    if hate[t2]=0 then hate[t2]:=t1;
    x:=getfather(hate[t1]);
    father[x]:=t2;
    x:=getfather(hate[t2]);
    father[x]:=t1;
   end;
 end;
for i:=1 to n do final[i]:=getfather(i);
qsort(1,n);
for i:=1 to n do inc(tot[final[i]]);
for i:=1 to n do
 begin
  t1:=final[i];
  if tot[t1]<>0 then begin

  if (hate[t1]<>0) and (not use[t1]) then
   begin
    if tot[t1]>tot[getfather(hate[t1])] then ans1:=ans1+tot[t1]
    else ans1:=ans1+tot[getfather(hate[t1])];
    use[t1]:=true;
    use[getfather(hate[t1])]:=true;
   end;
  if hate[t1]=0 then ans1:=ans1+tot[t1];

  end;
 end;
writeln(ans1);
//close(input);
//close(output);
end.

（靠数据两次AC我也是伪了……）

（最近写题目的得分率真不是很高啊……NO 一次AC在复赛可是不行的啊……）

（早点改变这个状态吧！）

10.30

USACO2014OPEN牧场装饰（bronzeT3）