|
|
|
|
|
|
洛克索耶夫
积分：1236
提交：341 / 501
|
|
|
这是稀疏图。。。prim暴力60分，kruskal暴力100分。
|
|
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
int totnum,tot,fa[502];
int n,m,x,y,q[502],kl;
bool b[502];
struct dd
{
int kaishi,zhong,juli;
int id;
}jie[5000];
int comp1(const dd &a,const dd &b)
{ if(a.juli==b.juli) return a.kaishi<b.kaishi;
return a.juli<b.juli;
}
int find(int x)
{
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
inline int in()
{
char c=getchar();
int x=0;
while(c<'0'||c>'9') c=getchar();
for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
return x;
}
bool KUR(int t){
sort(jie+1,jie+t+1,comp1);
int num=0;
totnum=0;
kl=0;
memset(b,0,sizeof(b));
for(int j=1;j<=n;++j) fa[j]=j;
for(int j=1;j<=t;++j)
{ int hi=jie[j].kaishi;
int hj=jie[j].zhong;
int yu=find(hj);
int lin=find(hi);
if(yu!=lin)
{
fa[yu]=lin;
totnum+=jie[j].juli;
num++;
q[++kl]=jie[j].id;
}
if(num==n-1)
return true;
}
return false;
}
int main()
{ /*freopen("road.in","r",stdin);
freopen("road.out","w",stdout);*/
n=in();
m=in();
for(int i=1;i<=m;++i)
{
jie[i].kaishi=in();
jie[i].zhong=in();
jie[i].juli=in();
jie[i].id=i;
if(i<n-1)
{
printf("0\n");
continue;
}
else
{
if(!KUR(i)){
printf("0\n");
continue;
}
else{
double fg=(double)totnum/2;
printf("%.1lf ",fg);
sort(q+1,q+kl+1);
for(int h=1;h<=kl;++h)
printf("%d ",q[h]);
printf("\n");
}
}
}
}
附上输出编号的代码
|
神利·代目
积分：3121
提交：803 / 1626
|
|
ztx
积分：2211
提交：758 / 1351
|
|
|
在自己电脑上没问题 交上去说运行时错误 求大神解答
|
|
TREAP套kruscal的飘过………… 
|
|
...本以为是动态维护的MST..但是看这个数据范围..........直接暴力即可啊m^2logm....谁告诉不可以么
|
|
|