HDU 3371 Connect the Cities(Prim,Kruskal)

タイトルアドレス:クリックしてリンクを開く
标题:あなたにたくさんの都市をあげて、それから津波が来て、津波が終わっていくつかの都市はつながっていて、すべての都市を最小の費用につなぐのはいくらですかを聞きます
構想:Kruskalアルゴリズムは無数の発を超えて、それからprimアルゴリズムを変えて、津波の後で、1つの都市の間の距離を0にすればいいことにつながって、C++で提出します
ACコード:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>

using namespace std;

const int maxn = 510;
const int zui = 0x3f3f3f3f;
int lowdist[maxn];
int map1[maxn][maxn];
int visit[maxn];
int n,m,k,sum;
bool flag;

void Prim()
{
    int i,j,k;
    memset(visit,0,sizeof(visit));
    for(i=1; i<=n; i++)
    {
        lowdist[i] = map1[1][i];
    }
    visit[1] = 1;
    sum = 0;
    for(i=1; i<n; i++)
    {
        int min1 = zui;
        for(j=1; j<=n; j++)
        {
            if(!visit[j] && lowdist[j] < min1)
            {
                min1 = lowdist[j];
                k = j;
            }
        }
        if(min1 == zui)
        {
            flag = false;
            return;
        }
        visit[k] = 1;
        sum += lowdist[k];
        for(j=1; j<=n; j++)
        {
            if(!visit[j] && map1[k][j] < lowdist[j])
            {
                lowdist[j] = map1[k][j];
            }
        }
    }
}

int main()
{
    int t;
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        flag = true;
        memset(map1,zui,sizeof(map1));
        scanf("%d%d%d",&n,&m,&k);
        int p,q,c;
        for(i=1; i<=m; i++)
        {
            scanf("%d%d%d",&p,&q,&c);
            if(c < map1[p][q])
            {
                map1[p][q] = map1[q][p] = c;
            }
        }
        int l,temp,x;
        for(i=1; i<=k; i++)
        {
            scanf("%d%d",&l,&temp);
            for(j=1; j<l; j++)
            {
                scanf("%d",&x);
                map1[temp][x] = map1[x][temp] = 0;
            }
        }
        Prim();
        if(flag)
        {
            printf("%d
",sum);
        }
        else
        {
            printf("-1
");
        }
    }
    return 0;
}

ACコード2:最初はG++で投げたTで、コード1と何の違いもなく初期化はループ文で、その後コード1はC++から使って、それからこのコードもC++で投げてみて、過ぎて、でも時間はコード1より少し長いです

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>

using namespace std;

const int maxn = 510;
const int zui = 1000000000;
int lowdist[maxn];
int map1[maxn][maxn];
int visit[maxn];
int n,m,k,sum;
bool flag;

void Prim()
{
    int i,j,k;
    memset(visit,0,sizeof(visit));
    for(i=1; i<=n; i++)
    {
        lowdist[i] = map1[1][i];
    }
    visit[1] = 1;
    sum = 0;
    for(i=1; i<n; i++)
    {
        int min1 = zui;
        for(j=1; j<=n; j++)
        {
            if(!visit[j] && lowdist[j] < min1)
            {
                min1 = lowdist[j];
                k = j;
            }
        }
        if(min1 == zui)
        {
            flag = false;
            return;
        }
        visit[k] = 1;
        sum += lowdist[k];
        for(j=1; j<=n; j++)
        {
            if(!visit[j] && map1[k][j] < lowdist[j])
            {
                lowdist[j] = map1[k][j];
            }
        }
    }
}

int main()
{
    int t;
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        flag = true;
        scanf("%d%d%d",&n,&m,&k);
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                map1[i][j] = zui;
            }
            map1[i][i] = 0;
        }
        int p,q,c;
        for(i=1; i<=m; i++)
        {
            scanf("%d%d%d",&p,&q,&c);
            if(c < map1[p][q])
            {
                map1[p][q] = map1[q][p] = c;
            }
        }
        int l,temp,x;
        for(i=1; i<=k; i++)
        {
            scanf("%d%d",&l,&temp);
            for(j=1; j<l; j++)
            {
                scanf("%d",&x);
                map1[temp][x] = map1[x][temp] = 0;
            }
        }
        Prim();
        if(flag)
        {
            printf("%d
",sum);
        }
        else
        {
            printf("-1
");
        }
    }
    return 0;
}

最終ポイントKruskalのタイムアウトコード
タイムアウトコード1:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>

using namespace std;

const int maxn = 510;
const int zui = 1000000000;
int lowdist[maxn];
int map1[maxn][maxn];
int visit[maxn];
int n,m,k,sum;
bool flag;

void Prim()
{
    int i,j,k;
    memset(visit,0,sizeof(visit));
    for(i=1; i<=n; i++)
    {
        lowdist[i] = map1[1][i];
    }
    visit[1] = 1;
    sum = 0;
    for(i=1; i<n; i++)
    {
        int min1 = zui;
        for(j=1; j<=n; j++)
        {
            if(!visit[j] && lowdist[j] < min1)
            {
                min1 = lowdist[j];
                k = j;
            }
        }
        if(min1 == zui)
        {
            flag = false;
            return;
        }
        visit[k] = 1;
        sum += lowdist[k];
        for(j=1; j<=n; j++)
        {
            if(!visit[j] && map1[k][j] < lowdist[j])
            {
                lowdist[j] = map1[k][j];
            }
        }
    }
}

int main()
{
    int t;
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        flag = true;
        scanf("%d%d%d",&n,&m,&k);
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                map1[i][j] = zui;
            }
            map1[i][i] = 0;
        }
        int p,q,c;
        for(i=1; i<=m; i++)
        {
            scanf("%d%d%d",&p,&q,&c);
            if(c < map1[p][q])
            {
                map1[p][q] = map1[q][p] = c;
            }
        }
        int l,temp,x;
        for(i=1; i<=k; i++)
        {
            scanf("%d%d",&l,&temp);
            for(j=1; j<l; j++)
            {
                scanf("%d",&x);
                map1[temp][x] = map1[x][temp] = 0;
            }
        }
        Prim();
        if(flag)
        {
            printf("%d
",sum);
        }
        else
        {
            printf("-1
");
        }
    }
    return 0;
}

k判環でタイムアウトして、n判環に変えて、中は1つのfor循環が少なくて、時間はとても少ないはずです
タイムアウトコード2:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>

using namespace std;

int pre[510];

struct node
{
    int left,right,value;
}a[25010];

int cmp(const void *_a,const void *_b)
{
    struct node *a = (node*)_a;
    struct node *b = (node*)_b;
    return a->value - b->value;
}

int findroot(int x)
{
    return x == pre[x] ? x : pre[x] = findroot(pre[x]);//         
}

int main()
{
    int t,n,m,k;
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(i=1; i<=n; i++)
        {
            pre[i] = i;
        }
        for(i=0; i<m; i++)
        {
            scanf("%d%d%d",&a[i].left,&a[i].right,&a[i].value);
        }
        qsort(a,m,sizeof(node),cmp);
        int sum,l,x;
        int root1,root2;
        for(i=0; i<k; i++)
        {
            scanf("%d",&sum);
            scanf("%d",&l);
            root1 = findroot(l);
            for(j=1; j<sum; j++)
            {
                scanf("%d",&x);
                root2 = findroot(x);
                if(root1 != root2)
                {
                    pre[root2] = pre[root1];
                    n--;
                }
            }
        }
        sum = 0;
        for(i=0; i<m; i++)
        {
            root1 = findroot(a[i].left);
            root2 = findroot(a[i].right);
            if(root1 != root2)
            {
                sum += a[i].value;
                pre[root1] = root2;
                n--;
            }
            if(n == 1)
                break;
        }
        if(n == 1)
        {
            printf("%d
",sum);
        }
        else
        {
            printf("-1
");
        }
    }
    return 0;
}

n判環で相変わらず超
タイムアウトコード3:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>

using namespace std;

int pre[510];

struct node
{
    int left,right,value;
}a[25010];

int cmp(const void *_a,const void *_b)
{
    struct node *a = (node*)_a;
    struct node *b = (node*)_b;
    return a->value - b->value;
}

int findroot(int x)
{
    return x == pre[x] ? x : pre[x] = findroot(pre[x]);//         
}

int main()
{
    int t,n,m,k;
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(i=1; i<=n; i++)
        {
            pre[i] = i;
        }
        for(i=0; i<m; i++)
        {
            scanf("%d%d%d",&a[i].left,&a[i].right,&a[i].value);
        }
        qsort(a,m,sizeof(node),cmp);
        int sum,l,x;
        int root1,root2;
        for(i=0; i<k; i++)
        {
            scanf("%d",&sum);
            scanf("%d",&l);
            root1 = findroot(l);
            for(j=1; j<sum; j++)
            {
                scanf("%d",&x);
                root2 = findroot(x);
                if(root1 != root2)
                {
                    pre[root2] = pre[root1];
                    n--;
                }
            }
        }
        sum = 0;
        for(i=0; i<m; i++)
        {
            if(pre[a[i].left] != pre[a[i].right])
            {
                pre[pre[a[i].left]] = pre[a[i].right];
                sum += a[i].value;
                n--;
            }
            if(n == 1)
                break;
        }
        if(n == 1)
        {
            printf("%d
",sum);
        }
        else
        {
            printf("-1
");
        }
    }
    return 0;
}

減少関数呼び出しは依然としてタイムアウト