/ Vijos / 题库 / 繁忙的都市 /

题解

114 条题解

  • 0
    @ 2013-12-16 13:43:06

    vijos跟我多大仇= =
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    int tim,a,b,c,N,M,tot,p[1000];
    struct road{
    int s,e,w;
    };
    road map[90010];
    bool cmp(road a,road b){
    return a.w<b.w;
    }
    int relax(int a){
    if(p[a]!=a) p[a]=relax(p[a]);
    return p[a];
    }
    int main(){
    cin>>N>>M;
    for(int i=1;i<=M;i++){
    cin>>a>>b>>c;
    map[i].s=a;
    map[i].e=b;
    map[i].w=c;
    }
    sort(map+1,map+M+1,cmp);
    for(int i=1;i<=N;i++) p[i]=i;
    for(int i=1;i<=M;i++){
    int x=relax(map[i].s),y=relax(map[i].e);
    if(x!=y){
    if(map[i].w>tot) tot=map[i].w;
    tim++;
    p[x]=y;
    }
    }
    cout<<N-1<<" "<<tot<<endl;
    // system("pause");
    return 0;
    }

  • 0
    @ 2013-12-16 13:42:04

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    int tim,a,b,c,N,M,tot,p[1000];
    struct road{
    int s,e,w;
    };
    road map[90010];
    bool cmp(road a,road b){
    return a.w<b.w;
    }
    int relax(int a){
    if(p[a]!=a) p[a]=relax(p[a]);
    return p[a];
    }
    int main(){
    cin>>N>>M;
    for(int i=1;i<=M;i++){
    cin>>a>>b>>c;
    map[i].s=a;
    map[i].e=b;
    map[i].w=c;
    }
    sort(map+1,map+M+1,cmp);
    for(int i=1;i<=N;i++) p[i]=i;
    for(int i=1;i<=M;i++){
    int x=relax(map[i].s),y=relax(map[i].e);
    if(x!=y){
    if(map[i].w>tot) tot=map[i].w;
    tim++;
    p[x]=y;
    }
    }
    cout<<N-1<<" "<<tot<<endl;
    // system("pause");
    return 0;
    }

  • 0
    @ 2013-12-16 13:41:09

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    int tim,a,b,c,N,M,tot,p[1000];
    struct road{
    int s,e,w;
    };
    road map[90010];
    bool cmp(road a,road b){
    return a.w<b.w;
    }
    int relax(int a){
    if(p[a]!=a) p[a]=relax(p[a]);
    return p[a];
    }
    int main(){
    cin>>N>>M;
    for(int i=1;i<=M;i++){
    cin>>a>>b>>c;
    map[i].s=a;
    map[i].e=b;
    map[i].w=c;
    }
    sort(map+1,map+M+1,cmp);
    for(int i=1;i<=N;i++) p[i]=i;
    for(int i=1;i<=M;i++){
    int x=relax(map[i].s),y=relax(map[i].e);
    if(x!=y){
    if(map[i].w>tot) tot=map[i].w;
    tim++;
    p[x]=y;
    }
    }
    cout<<N-1<<" "<<tot<<endl;
    // system("pause");
    return 0;
    }
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    int tim,a,b,c,N,M,tot,p[1000];
    struct road{
    int s,e,w;
    };
    road map[90010];
    bool cmp(road a,road b){
    return a.w<b.w;
    }
    int relax(int a){
    if(p[a]!=a) p[a]=relax(p[a]);
    return p[a];
    }
    int main(){
    cin>>N>>M;
    for(int i=1;i<=M;i++){
    cin>>a>>b>>c;
    map[i].s=a;
    map[i].e=b;
    map[i].w=c;
    }
    sort(map+1,map+M+1,cmp);
    for(int i=1;i<=N;i++) p[i]=i;
    for(int i=1;i<=M;i++){
    int x=relax(map[i].s),y=relax(map[i].e);
    if(x!=y){
    if(map[i].w>tot) tot=map[i].w;
    tim++;
    p[x]=y;
    }
    }
    cout<<N-1<<" "<<tot<<endl;
    // system("pause");
    return 0;
    }
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    int tim,a,b,c,N,M,tot,p[1000];
    struct road{
    int s,e,w;
    };
    road map[90010];
    bool cmp(road a,road b){
    return a.w<b.w;
    }
    int relax(int a){
    if(p[a]!=a) p[a]=relax(p[a]);
    return p[a];
    }
    int main(){
    cin>>N>>M;
    for(int i=1;i<=M;i++){
    cin>>a>>b>>c;
    map[i].s=a;
    map[i].e=b;
    map[i].w=c;
    }
    sort(map+1,map+M+1,cmp);
    for(int i=1;i<=N;i++) p[i]=i;
    for(int i=1;i<=M;i++){
    int x=relax(map[i].s),y=relax(map[i].e);
    if(x!=y){
    if(map[i].w>tot) tot=map[i].w;
    tim++;
    p[x]=y;
    }
    }
    cout<<N-1<<" "<<tot<<endl;
    // system("pause");
    return 0;
    }

  • 0
    @ 2013-12-16 13:38:39

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n,m;
    int ans,tot;
    int a,b,c;
    int f[1000],deep[1000];
    struct abc
    {
    int x;
    int y;
    int z;
    };
    abc map[90000];
    bool cmp(abc d,abc e)
    {
    return d.z<e.z;
    }
    int find(int d)
    {
    if (f[d]!=d) f[d]=find(f[d]);
    return f[d];
    }
    void hebing(int d,int e)
    {
    int i=find(d);int j=find(e);
    f[i]=j;
    }
    int main()
    {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {f[i]=i;deep[i]=1;}
    for(int i=1;i<=m;i++)
    {
    cin>>a>>b>>c;
    map[i].x=a;
    map[i].y=b;
    map[i].z=c;
    }
    sort(map+1,map+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
    if (find(map[i].x)!=find(map[i].y))
    {
    if (map[i].z>ans) ans=map[i].z;
    hebing(map[i].x,map[i].y);

    }

    }
    cout<<n-1<<" "<<ans<<endl;
    return 0;
    }

  • 0
    @ 2013-11-04 21:04:43

    。。。。裸题。。。。可惜速度略渣。。。

    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 2100 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 2104 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 2096 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 2096 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 2100 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 2104 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 2104 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 2104 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 2104 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 2104 KiB, score = 10
    Accepted, time = 90 ms, mem = 2104 KiB, score = 100

    #include <cstdio>
    #include <algorithm>
    #include <cstring>

    using namespace std;

    #define MAXN 100010

    struct saver {
    int s,t,d;
    } edge[MAXN];

    bool cmp(saver x,saver y) {
    return x.d<y.d;
    }

    int n,m,father[MAXN];

    int Find(int x) {
    int i,j=x;
    for (i=x;father[i];i=father[i]) ;
    while (father[j]) {
    int k=father[j];
    father[j]=i;
    j=k;
    }
    return i;
    }

    int main() {
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++) scanf("%d%d%d",&edge[i].s,&edge[i].t,&edge[i].d);
    sort(edge,edge+m,cmp);
    memset(father,0,sizeof(father));
    printf("%d ",n-1);
    for (int i=0;i<m;i++) {
    if (Find(edge[i].s)!=Find(edge[i].t)) {
    father[Find(edge[i].s)]=Find(edge[i].t);
    if ((--n)==1) {
    printf("%d\n",edge[i].d);
    return 0;
    }
    }
    }
    return 0;
    }

  • 0
    @ 2013-10-20 20:07:44

    kus秒杀。
    刷水题，练手感。
    争取拿到题目，闭着眼睛就会做！~
    做完不用编译，直接AC！~
    我知道这只是梦想。
    但我会努力实现它的！~
    DXE-SYF

  • 0
    @ 2013-10-20 09:12:39

    裸的prim

  • 0
    @ 2013-03-25 15:33:44

    各位大神：其实根本不用prim。。。。只需要dfs查看一下是否能生成就可以了。。。这是我用邻接表写的的时间

    上海红茶馆 via libjudge
    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 1064 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1064 KiB, score = 10
    测试数据 #2: Accepted, time = 30 ms, mem = 1064 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1064 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 1064 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 1064 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 1064 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 1064 KiB, score = 10
    测试数据 #8: Accepted, time = 31 ms, mem = 1064 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 1064 KiB, score = 10
    Summary: Accepted, time = 151 ms, mem = 1064 KiB, score = 100

  • 0
    @ 2012-08-23 12:37:48

    #01: ---|---|---|---|---|---|---|---|-

    Accepted (0ms, 308KB)

    #02: ---|---|---|---|---|---|---|---|-

    Accepted (0ms, 308KB)

    #03: ---|---|---|---|---|---|---|---|-

    Accepted (0ms, 308KB)

    #04: ---|---|---|---|---|---|---|---|-

    Accepted (0ms, 308KB)

    #05: ---|---|---|---|---|---|---|---|-

    Accepted (0ms, 308KB)

    #06: ---|---|---|---|---|---|---|---|-

    Accepted (0ms, 308KB)

    #07: ---|---|---|---|---|---|---|---|-

    Accepted (0ms, 308KB)

    #08: ---|---|---|---|---|---|---|---|-

    Accepted (0ms, 308KB)

    #09: ---|---|---|---|---|---|---|---|-

    Accepted (0ms, 308KB)

    #10: ---|---|---|---|---|---|---|---|-

    Accepted (0ms, 308KB)

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 0ms / 308KB

    kruskal AC...

  • 0
    @ 2010-07-13 17:58:22

    此题很水，只需二分答案，然后判断是否能够成一棵树即可。

  • 0
    @ 2009-11-10 17:27:05

    权当是练习prim 了

  • 0
    @ 2009-11-09 20:37:41

    555...我是554通过的...

  • 0
    @ 2009-11-09 15:33:08

    农夫山泉.......

    居然难度3？！

  • 0
    @ 2009-11-09 15:28:41

    好久没编 prim 了

    练了下手

  • 0
    @ 2009-11-07 15:05:13

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    prim 也能过？

  • 0
    @ 2009-11-07 00:03:36

    program p1190;

    var i,x,y,c,n,m,j,ans:longint;

    cost:array[1..300,1..300]of longint;

    lowcost:array

    [1..1000]of longint;

    procedure prim(v0:longint);

    var i,j,k,min:longint;

    begin

    ans:=0;

    for i:=1 to n do lowcost[i]:=cost[v0,i];

    for i:=1 to n do cost:=maxlongint;

    for i:=1 to n-1 do

    begin

    min:=maxlongint;

    k:=0;

    for j:=1 to n do

    if (lowcost[j]ans then ans:=lowcost[k];

    lowcost[k]:=maxlongint;

    for j:=1 to n do cost[j,k]:=maxlongint;

    for j:=1 to n do

    if (cost[k,j]

  • 0
    @ 2009-11-06 20:27:48

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    这一道题目根本就不是最小生成树的题目（虽然可以用最小生成树的prim或者是kruskal算法解决），我只用了并查集+二分答案，秒杀，连快排都省了：

    below is my code:

    program p1190;

    type

    node=record

    u,v,c:integer;

    end;

    shuzu=array[1..70000] of node;

    var

    e:shuzu;

    fa:array[1..400] of integer;

    n,m,i,l,r,mid,max:integer;

    function getfa(x:integer):integer;

    begin

    if fa[x]=x then exit(x)

    else fa[x]:=getfa(fa[x]);

    exit(fa[x]);

    end;

    function isok(max:longint):boolean;

    var

    i:longint;

    tot,xx,yy:integer;

    begin

    for i:=1 to n do fa[i]:=i;

    tot:=0;

    for i:=1 to m do

    begin

    xx:=getfa(e[i].u); yy:=getfa(e[i].v);

    if (xxyy) and (e[i].c

  • 0
    @ 2009-11-03 19:59:54

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    prim

  • 0
    @ 2009-11-02 17:20:07

    kruscal才是王道。。。

  • 0
    @ 2009-11-02 16:53:40

    开1000习惯了...又开小了。

    裸的PRIM，小心点写就没问题。

繁忙的都市

信息

ID
1190
难度
5
分类
树结构 | 生成树 点击显示
标签
递交数
2962
已通过
1132
通过率
38%
被复制
7
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1