HDU3371--- Connect the Cities

996 ワード

とても卵の痛い問題で、この問題は運を見ることができなくて、運が700 msよくて、運が悪くてタイムアウトします.(あと998 msででたらめを言います--)
何度も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
"); } }