专栏首页HansBug's Lab3390: [Usaco2004 Dec]Bad Cowtractors牛的报复

3390: [Usaco2004 Dec]Bad Cowtractors牛的报复

3390: [Usaco2004 Dec]Bad Cowtractors牛的报复

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 69  Solved: 49

[Submit][Status][Discuss]

Description

    奶牛贝茜被雇去建设N(2≤N≤1000)个牛棚间的互联网.她已经勘探出M(1≤M≤

20000)条可建的线路,每条线路连接两个牛棚,而且会苞费C(1≤C≤100000).农夫约翰吝啬得很,他希望建设费用最少甚至他都不想给贝茜工钱. 贝茜得知工钱要告吹,决定报复.她打算选择建一些线路,把所有牛棚连接在一起,让约翰花费最大.但是她不能造出环来,这样约翰就会发现.

Input

  第1行:N,M.

  第2到M+1行:三个整数,表示一条可能线路的两个端点和费用.

Output

    最大的花费.如果不能建成合理的线路,就输出-1

Sample Input

5 8 1 2 3 1 3 7 2 3 10 2 4 4 2 5 8 3 4 6 3 5 2 4 5 17

Sample Output

42 连接4和5,2和5,2和3,1和3,花费17+8+10+7=42

HINT

Source

Silver

题解:最小生成树模板题(HansBug:虽然准确来讲是最大生成树),感觉自己水水哒

 1 /**************************************************************
 2     Problem: 3390
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:56 ms
 7     Memory:1788 kb
 8 ****************************************************************/
 9  
10 var
11    i,j,k,l,m,n,x,ans:longint;
12    a:array[0..100005,1..3] of longint;
13    c:array[0..100005] of longint;
14 function getfat(x:longint):longint;
15          begin
16               if c[x]<>x then c[x]:=getfat(c[x]);
17               exit(c[x]);
18          end;
19 procedure swap(var x,y:longint);
20           var z:longint;
21           begin
22                z:=x;x:=y;y:=z;
23           end;
24 procedure sort(l,r:longint);
25           var i,j,x,y:longint;
26           begin
27                i:=l;j:=r;x:=a[(l+r) div 2,3];
28                repeat
29                      while a[i,3]>x do inc(i);
30                      while a[j,3]<x do dec(j);
31                      if i<=j then
32                         begin
33                              swap(a[i,1],a[j,1]);
34                              swap(a[i,2],a[j,2]);
35                              swap(a[i,3],a[j,3]);
36                              inc(i);dec(j);
37                         end;
38                until i>j;
39                if i<r then sort(i,r);
40                if l<j then sort(l,j);
41           end;
42  
43 {$IFDEF WINDOWS}{$R bzoj3390.rc}{$ENDIF}
44  
45 begin
46      readln(n,m);
47      for i:=1 to n do c[i]:=i;
48      for i:=1 to m do readln(a[i,1],a[i,2],a[i,3]);
49      sort(1,m);
50      j:=1;x:=0;
51      for i:=1 to n-1 do
52          begin
53               while j<=m do
54                     begin
55                          k:=getfat(a[j,1]);
56                          l:=getfat(a[j,2]);
57                          if k<>l then break;
58                          inc(j);
59                     end;
60               if k=l then break;
61               ans:=ans+a[j,3];
62               c[k]:=l;inc(j);
63               inc(x);
64          end;
65      if x<(n-1) then writeln(-1) else writeln(ans);
66      readln;
67 end.      

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3631: [JLOI2014]松鼠的新家

    3631: [JLOI2014]松鼠的新家 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 707  Solv...

    HansBug
  • 2929: [Poi1999]洞穴攀行

    2929: [Poi1999]洞穴攀行 Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 80  Solved: ...

    HansBug
  • 1622: [Usaco2008 Open]Word Power 名字的能量

    1622: [Usaco2008 Open]Word Power 名字的能量 Time Limit: 5 Sec  Memory Limit: 64 MB Su...

    HansBug
  • 1339 / 1163: [Baltic2008]Mafia

    1163: [Baltic2008]Mafia Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 96  Sol...

    HansBug
  • 1622: [Usaco2008 Open]Word Power 名字的能量

    1622: [Usaco2008 Open]Word Power 名字的能量 Time Limit: 5 Sec  Memory Limit: 64 MB Su...

    HansBug
  • 3401: [Usaco2009 Mar]Look Up 仰望

    3401: [Usaco2009 Mar]Look Up 仰望 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: ...

    HansBug
  • 1934: [Shoi2007]Vote 善意的投票

    1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 1174  ...

    HansBug
  • 算法模板——线段树3(区间覆盖值+区间求和)

    实现功能——1:区间覆盖值;2:区间求和 相比直接的区间加,这个要注重顺序,因为操作有顺序之分。所以这里面的tag应该有个pushup操作(本程序中的ext) ...

    HansBug
  • 算法模板——线段树5(区间开根+区间求和)

    实现功能——1:区间开根;2:区间求和(此模板以BZOJ3038为例) 作为一个非常规的线段树操作,其tag也比较特殊呵呵哒 1 var 2 i,j,...

    HansBug
  • 2243: [SDOI2011]染色

    2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MB Submit: 3113  Solved...

    HansBug

扫码关注云+社区

领取腾讯云代金券