- 繁忙的都市
- 12 年前 @
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
const int maxm=90000,maxn=300;
int first[maxn];
int u[maxm],v[maxm],w[maxm],ans,r[maxm],p[maxm],n,m,next[maxm],s;
bool choose[maxm];
int find(int k){return((p[k]==k)?k:find(p[k]));}
int cmp(const int i,const int j){return w[i]<w[j];}
void kruskal()
{
s=0;ans=-1;
for (int i=1;i<=n;i++)p[i]=i;
for (int i=0;i<2*m;i++)r[i]=i;
sort(r,r+m*2,cmp);
for (int i=0;i<m*2;i++)
{
int e=r[i],x=find(u[e]),y=find(v[e]);
if (x!=y)
{
p[x]=y;
if (w[e]>ans)ans=w[e];
s++;
}
}
}
int main()
{
cin>>n>>m;
for (int i=0;i<m*2;i+=2)
{
cin>>u[i]>>v[i]>>w[i];
next[i]=first[u[i]];
first[u[i]]=i;
u[i+1]=v[i];v[i+1]=u[i];w[i+1]=w[i];
next[i+1]=first[u[i+1]];
first[u[i+1]]=i+1;
}
kruskal();
cout<<s<<" "<<ans;
}
测试数据 #0: Accepted, time = 61 ms, mem = 2428 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 2428 KiB, score = 10
测试数据 #2: Accepted, time = 46 ms, mem = 2428 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2428 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 2428 KiB, score = 10
测试数据 #5: Accepted, time = 30 ms, mem = 2428 KiB, score = 10
测试数据 #6: Accepted, time = 29 ms, mem = 2428 KiB, score = 10
测试数据 #7: Accepted, time = 30 ms, mem = 2428 KiB, score = 10
测试数据 #8: Accepted, time = 44 ms, mem = 2428 KiB, score = 10
测试数据 #9: Accepted, time = 44 ms, mem = 2428 KiB, score = 10
Summary: Accepted, time = 314 ms, mem = 2428 KiB, score = 100
10 条评论
-
ice1000 LV 6 @ 8 年前
补时间
-
8 年前@
我的代码更快,只有三个15ms
-
8 年前@
读入优化
-
12 年前@
ios::sync_with_stdio(false);
-
12 年前@
cin读入是很慢的,用scanf吧,或者把什么同步关掉,百度一下好了
-
12 年前@
这里好像保存数据上没有用链表的必要。。。
有些傻了。。。
删去链表之后的代码贴上:#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
const int maxm=90000,maxn=300;
int u[maxm],v[maxm],w[maxm],ans,r[maxm],p[maxm],n,m,s;
bool choose[maxm];
int find(int k){return((p[k]==k)?k:find(p[k]));}
int cmp(const int i,const int j){return w[i]<w[j];}
void kruskal()
{
s=0;ans=-1;
for (int i=1;i<=n;i++)p[i]=i;
for (int i=0;i<2*m;i++)r[i]=i;
sort(r,r+m*2,cmp);
for (int i=0;i<m*2;i++)
{
int e=r[i],x=find(u[e]),y=find(v[e]);
if (x!=y)
{
p[x]=y;
if (w[e]>ans)ans=w[e];
s++;
}
}
}
int main()
{
cin>>n>>m;
for (int i=0;i<m*2;i+=2)
{
cin>>u[i]>>v[i]>>w[i];
u[i+1]=v[i];v[i+1]=u[i];w[i+1]=w[i];
}
kruskal();
cout<<s<<" "<<ans;
}
不过按照常理说,这样应该更快吧,事实竟然很残酷。。。
测试数据 #0: Accepted, time = 105 ms, mem = 2080 KiB, score = 10
测试数据 #1: Accepted, time = 31 ms, mem = 2080 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 2080 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 2080 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 2080 KiB, score = 10
测试数据 #5: Accepted, time = 30 ms, mem = 2080 KiB, score = 10
测试数据 #6: Accepted, time = 44 ms, mem = 2080 KiB, score = 10
测试数据 #7: Accepted, time = 43 ms, mem = 2080 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 2080 KiB, score = 10
测试数据 #9: Accepted, time = 74 ms, mem = 2080 KiB, score = 10
Summary: Accepted, time = 434 ms, mem = 2080 KiB, score = 100
为什么时间更长了呢? -
12 年前@
构思了一下觉得可以用桶排,利用哈希解决冲突的方法解决冲突问题,注意把数组开大一点,这样或许会更快
-
12 年前@
为什么要用链表?
刚打了一个也没到0ms,话说楼下说用spfa,恕我愚钝我怎么都想不到用spfa请指教
测试数据 #0: Accepted, time = 15 ms, mem = 1256 KiB, score = 10测试数据 #1: Accepted, time = 0 ms, mem = 1256 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 1256 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 1256 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1256 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 1256 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1256 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 1256 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1256 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 1256 KiB, score = 10
Summary: Accepted, time = 105 ms, mem = 1256 KiB, score = 100
#include <cstdio>
#include <algorithm>
using namespace std;
struct xxx{
int x,y,val;
}a[90001];
int n,m,f[301],l,MX;
int getfather(int v){
if(f[v]==v)return v;
else return f[v]=getfather(f[v]);
}
bool cmp(const xxx &a,const xxx &b){return a.val<b.val;}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;++i)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].val);
sort(a+1,a+1+m,cmp);
for (int i=1;i<=n;++i)f[i]=i;
for (int i=1;i<=m;++i)
if(getfather(a[i].x)!=getfather(a[i].y)){
f[f[a[i].y]]=f[a[i].x];
++l;
MX=max(a[i].val,MX);
}
printf("%d %d\n",l,MX);
} -
12 年前@
@vistaswx 哪台是超算?
-
12 年前@
你需要spfa
- 1