HDU3371--- Connect the Cities
996 ワード
とても卵の痛い問題で、この問題は運を見ることができなくて、運が700 msよくて、運が悪くてタイムアウトします.(あと998 msででたらめを言います--)
何度もint cmp()速度をbool cmp()速度より少し速くテストした.
パス圧縮を使わないほうが早いです...
何度もint cmp()速度をbool cmp()速度より少し速くテストした.
パス圧縮を使わないほうが早いです...
#include
#include
#include
using namespace std;
#define ll long long
#define inf 0xfffff
#define MAX 25500
int p[510],n,m,s,kk,flag;
struct e
{
int a,b,c;
};
e path[MAX];
bool cmp(const e &a, const e &b)
{
return a.c1;i++) // c==1
{
int dx=find(path[i].a);
int dy=find(path[i].b);
if(dx!=dy)
{
sum+=path[i].c;
p[dx]=dy;
flag--;
}
}
if(flag==1)
printf("%d
",sum);
else
printf("-1
");
}
}