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("%dn",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.
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602435.html