hdu--1232 继续通畅工程

wa了8次，超级崩溃，险些自闭，不过倒是学到了很多，先来一段代码：

#include<bits/stdc++.h>
using namespace std;
int p[1000];            //储存查并集 
int n,m;
struct node{            //数组结构体，排序距离 
    int a,b;
    int d;
}v[100000];
bool cmp(node x,node y)
{
    return x.d<y.d;
}
int find(int x)
{
    int re=x;
    while(p[re]!=re)
    {
        re=p[re];
    }
    return re;
}
void join(int x,int y)
{
    int dx=find(x);
    int dy=find(y);
    if(dx!=dy)
    p[dx]=dy;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n && n)          //N(N-1)/2条路，n个村庄，n！=0 
    {
        m=n*(n-1)/2;
        for(int i=1;i<=n;i++)    //初始化p 
            p[i]=i;
        for(int i=0;i<m;i++)        //N(N-1)/2组输入 
            scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].d);  //输入 
        sort(v,v+m,cmp);         //排序距离，从小到大 
        int sum=0;
        for(int i=0;i<m;i++)
        {
            if(find(v[i].a)!=find(v[i].b))   //if此时最小距离代表的两个村庄间不连通 
            {
                join(v[i].a,v[i].b);                   //连通这两个村庄 
                sum+=v[i].d;              //总距离+ 此时最小距离
            }
        }    
        printf("%d\n",sum);
    }
    return 0;
}

首先不用管最后hint，这道题就用cin,cout就可以过

其次是这个加速c++输入的语句，用前1300ms，用后300ms，妈妈再也不用担心我的没法飙车了

ios::sync_with_stdio(false);

加速，加速！（~耶~~逮虾户~~）

再然后，就是这个函数最好不要和scanf连用，否则会疯狂的wa wa(比如上述代码>_<)。

最后一点就是这个并查集，最小生成树的模板要记住。

以上。

———2019/8/5 13:04:47；

——再加一点，对于ios::sync_with_stdio(false);

在NOIP的评测机上这样子会爆0 
因此，noip比赛中坚决不要写std::ios::sync_with_stdio(false) 
爆0的原因如下 
noip明确要求使用freopen,而freopen是stdio库中的,既然我们已经取消了iostream和stdio的同步,这样会造成文件指针混乱,进而导致RE1111

最后详情-Here.

 

原文链接:https://www.cnblogs.com/zjydeoneday/p/11302366.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有