POJ3723 《挑战程序设计竞赛》踩坑

我看书上的代码,觉得这一行有错误,

//这里为什么要加上女生的人数而不是男生的人数?我认为应该加男生的人数
 es[j].v = v+N;

所以我就没这样写,我写的是

es[j].v = v+M;

在codeblocks运行的好好的,来了poj一直报错,debug两个多小时,终于发现,书里的题目和poj上的题目,x,y表示的正好相反啊啊啊啊啊啊啊!!!!!!!!! 书里说,(x,y,d)表示的是第x号男兵和第y号女兵的亲密度是d poj的原题说的是第x号女兵和第y号男兵的亲密度是d!!!


好了 容我歇会儿 附上AC的源码

#include <cstdio>
#include <algorithm>
#define MAX 10000
using namespace std;

int par[MAX*2];
int height[MAX*2];
int N,M,R;


void init_union_find(int v)
{
    for(int i=0;i<v;i++)
    {
        par[i]=i;
    }
    fill(height,height+v,0);
}
int  find_root(int x)
{
    if(par[x]==x)
    {
        return x;
    }
    return find_root(par[x]);
}
void unite(int x,int y)
{
    x = find_root(x);
    y = find_root(y);
    if(x==y)
    {
        return;
    }

    if(height[x]>height[y])
    {
        par[y]=x;
    }
    else
    {
        par[x]=y;
        if(height[x]==height[y])
        {
            height[y]++;
        }
    }
}
bool same(int x,int y)
{
    return find_root(x)==find_root(y);
}


struct edge {
    int u,v,cost;
};

bool comp(const edge& e1,const edge& e2)
{
    return e1.cost<e2.cost;
}
edge es[MAX*5];



int kruskal()
{
    sort(es,es+R,comp);
    init_union_find(N+M);
    int res = 0;
    for(int i=0;i<R;i++)
    {
        edge e = es[i];
        //printf("edge e :%d %d %d",es[i].u,es[i].v,es[i].cost);
        if(!same(e.u,e.v))
        {
            unite(e.u,e.v);
            res += e.cost;
        }
    }
    return res;
}

int main()
{
    int loop;
    scanf("%d",&loop);
    int u,v,cost;
    for(int i=0;i<loop;i++)
    {
        scanf("%d%d%d",&N,&M,&R);
        for(int j=0;j<R;j++)
        {
            scanf("%d%d%d",&u,&v,&cost);
            es[j].cost = -cost;
            es[j].u = u;
            //这里为什么要加上女生的人数而不是男生的人数?我认为应该加男生的人数
            es[j].v = v+N;
        }
        printf("%d\n",(N+M)*MAX+kruskal());
    }
    return 0;
}

AC万岁,过啥圣诞,要啥自行车。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老九学堂

第一次Java串讲

Java基础的知识点结构 “目无全牛 游刃有余” ? 2阶段复习巩固 老九学堂学Java微视频到此已经录制三讲了,我们计划是每二周做一次知识点的串讲,目的是帮...

30580
来自专栏calmound

匈牙利算法

今天学习了下匈牙利算法,发现这个早在几个月前学过的知识已经忘记的一干二净了,记得当初学习的时候只是看书,看论文,现在要好好的总结下,防止以后再次忘记。 此次总结...

49770
来自专栏应用案例

js实现快速排序

作者注:算法能力一直是程序猿最基础也是最重要的一项基础能力,记得Pascal之父、结构化程序设计的先驱Niklaus Wirth最著名的一本书,书名叫作《算法 ...

32080
来自专栏鸿的学习笔记

关于英语,也许你忽视了很多东西

这是葛传椝老先生对英语学习者的教导,通篇用易读的英文短文讲述了英语学习过程中的种种心得,其中“大都是英语语法书和英语修辞学书不曾提到的”,文短而词丰,言简而意赅...

10510
来自专栏牛客网

网易内推(C++/C研发)offer之路

      看到大家都在牛客上写面经,我也来凑一下热闹,本人是一所普通高校的研究生(非211,985高校),自动化专业(非计算机)。

14020
来自专栏牛客网

网易内推(C++/C研发)offer之路

看到大家都在牛客上写面经,我也来凑一下热闹,本人是一所普通高校的研究生(非211,985高校),自动化专业(非计算机)。 上个星期拿到了网易内推C++研发岗位的...

42790
来自专栏PPV课数据科学社区

排序在数据分析中有多重要?

说不会对数据排序的举手,所有的手都放下了。拿到数据,谁还不会排序吗?就连你在打牌时都在排序。 ? 可是这一小小的操作,在数据分析中到底有多重要,有人知道吗?我们...

31430
来自专栏CDA数据分析师

排序在数据分析中有多重要?

说不会对数据排序的举手,所有的手都放下了。拿到数据,谁还不会排序吗?就连你在打牌时都在排序。 ? 可是这一小小的操作,在数据分析中到底有...

19360
来自专栏tkokof 的技术,小趣及杂念

“快排”笔记

  关于排序,我想没有多少程序员会感觉陌生,信手拈来的可能就有不少:冒泡、选择或者归并等等;可在实际开发中,排序又让许多程序员感到很不熟悉,因为在大多数情况下,...

9130
来自专栏企鹅号快讯

为什么那么多人说C+难学?怎么学

对于正在学习C/C++的同学来说,C语言可能不难,但是当自学C++的时候,总会出现各种问题,就像是一个恶性循环不懂所以不想看,关键是没有·一个由浅到深的过程,刚...

20080

扫码关注云+社区

领取腾讯云代金券