2010-1066

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

Contest 1 Conference Call

结题报告。

  题目描述是说有一个电话网，每一个电话连在网中的一个节点上，一个节点可以连多个电话。网构成了一个无向图。题目数据给出了三个需要互相连通的电话，问怎样架设网络使他们连通。

  三个点连通显然有一个中心点，但是如果枚举中心点，那么时间复杂度为500(中心)*(500*500)(dijkstra)超时。考虑到求最短路只有对三个需求点的数据才有效，所以可以先以需求的三个点为源求出最短路，然后枚举中心点，复杂度为O(n!^ 2)。

  程序如下：三次最短路没有在一起写，直接复制粘贴了改改参数。

{{{
#!cpp
#include <cstdio>
#include <cstring>
int phone[10001];
int dis[501][501];
int disa[501];
int disb[501];
int disc[501];
int a,b,c;
int n,m,l;
void dija()
{
    int used[501]  ;
    memset(used,0,sizeof(used));
    for (int i=1;i<=m;i++)
        disa[i]=0xffffff;
    disa[a]=0;
    for (int i=1;i<=m;i++)
    {
        int min=0xffffff;
        int minindex=0;
        for (int i=1;i<=m;i++)
            if (used[i]&&disa[i]<min)
            {
                min=disa[i];
                minindex=i;
            }
        if(min==0xffffff)
            return;
        used[minindex]=true;
        for (int i=1;i<=m;i++)
            if (disa[minindex]+dis[minindex][i]<disa[i])
                disa[i]=disa[minindex]+dis[minindex][i];
    }
}
void dijb()
{
    int used[501]  ;
    memset(used,0,sizeof(used));
    for (int i=1;i<=m;i++)
        disb[i]=0xffffff;
    disb[b]=0;
    for (int i=1;i<=m;i++)
    {
        int min=0xffffff;
        int minindex=0;
        for (int i=1;i<=m;i++)
            if (used[i]&&disb[i]<min)
            {
                min=disb[i];
                minindex=i;
            }
        if(min==0xffffff)
            return;
        used[minindex]=true;
        for (int i=1;i<=m;i++)
            if (disb[minindex]+dis[minindex][i]<disb[i])
                disb[i]=disb[minindex]+dis[minindex][i];
    }
}
void dijc()
{
    int used[501]  ;
    memset(used,0,sizeof(used));
    for (int i=1;i<=m;i++)
        disc[i]=0xffffff;
    disc[c]=0;
    for (int i=1;i<=m;i++)
    {
        int min=0xffffff;
        int minindex=0;
        for (int i=1;i<=m;i++)
            if (used[i]&&disc[i]<min)
            {
                min=disc[i];
                minindex=i;
            }
        if(min==0xffffff)
            return;
        used[minindex]=true;
        for (int i=1;i<=m;i++)
            if (disc[minindex]+dis[minindex][i]<disc[i])
                disc[i]=disc[minindex]+dis[minindex][i];
    }
}
int main()
{
    int cases=0;
    while (scanf("%d %d %d",&n,&m,&l)!=EOF)
    {
        cases++;
        for (int i=1;i<=m;i++)
            for (int j=1;j<=m;j++)
                dis[i][j]=0xffffff;
        for (int i=1;i<=n;i++)
            scanf("%d",&phone[i]);
        for (int i=1;i<=l;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            dis[a][b]=c;
            dis[b][a]=c;
        }
        int p;
        scanf("%d",&p);
        printf("Case #%d\n",cases);
        for (int s=1;s<=p;s++)
        {
            scanf("%d%d%d",&a,&b,&c);
            a=phone[a];
            b=phone[b];
            c=phone[c];
            dija();         //求a为源最短路
            dijb();         //求b为源最短路
            dijc();         //求c为源最短路
            int min=0xffffff;
            for (int i=1;i<=m;i++)//枚举中心点
            {
                if (disa[i]+disb[i]+disc[i]<min)
                    min=disa[i]+disb[i]+disc[i];
            }
            if (min!=0xffffff)
                printf("Line %d: The minimum cost for this line is %d.\n",s,min);
            else
                printf("Line %d: Impossible to connect!\n",s);
        }
    }
}
}}}

Contest 1 Conference Call

结题报告。

题目描述是说有一个电话网，每一个电话连在网中的一个节点上，一个节点可以连多个电话。网构成了一个无向图。题目数据给出了三个需要互相连通的电话，问怎样架设网络使他们连通。

三个点连通显然有一个中心点，但是如果枚举中心点，那么时间复杂度为500(中心)*(500*500)(dijkstra)超时。考虑到求最短路只有对三个需求点的数据才有效，所以可以先以需求的三个点为源求出最短路，然后枚举中心点，复杂度为O(n!^ 2)。

程序如下：三次最短路没有在一起写，直接复制粘贴了改改参数。

#include <cstdio>
#include <cstring>
int phone[10001];
int dis[501][501];
int disa[501];
int disb[501];
int disc[501];
int a,b,c;
int n,m,l;
void dija()
{
    int used[501]  ;
    memset(used,0,sizeof(used));
    for (int i=1;i<=m;i++)
        disa[i]=0xffffff;
    disa[a]=0;
    for (int i=1;i<=m;i++)
    {
        int min=0xffffff;
        int minindex=0;
        for (int i=1;i<=m;i++)
            if (used[i]&&disa[i]<min)
            {
                min=disa[i];
                minindex=i;
            }
        if(min==0xffffff)
            return;
        used[minindex]=true;
        for (int i=1;i<=m;i++)
            if (disa[minindex]+dis[minindex][i]<disa[i])
                disa[i]=disa[minindex]+dis[minindex][i];
    }
}
void dijb()
{
    int used[501]  ;
    memset(used,0,sizeof(used));
    for (int i=1;i<=m;i++)
        disb[i]=0xffffff;
    disb[b]=0;
    for (int i=1;i<=m;i++)
    {
        int min=0xffffff;
        int minindex=0;
        for (int i=1;i<=m;i++)
            if (used[i]&&disb[i]<min)
            {
                min=disb[i];
                minindex=i;
            }
        if(min==0xffffff)
            return;
        used[minindex]=true;
        for (int i=1;i<=m;i++)
            if (disb[minindex]+dis[minindex][i]<disb[i])
                disb[i]=disb[minindex]+dis[minindex][i];
    }
}
void dijc()
{
    int used[501]  ;
    memset(used,0,sizeof(used));
    for (int i=1;i<=m;i++)
        disc[i]=0xffffff;
    disc[c]=0;
    for (int i=1;i<=m;i++)
    {
        int min=0xffffff;
        int minindex=0;
        for (int i=1;i<=m;i++)
            if (used[i]&&disc[i]<min)
            {
                min=disc[i];
                minindex=i;
            }
        if(min==0xffffff)
            return;
        used[minindex]=true;
        for (int i=1;i<=m;i++)
            if (disc[minindex]+dis[minindex][i]<disc[i])
                disc[i]=disc[minindex]+dis[minindex][i];
    }
}
int main()
{
    int cases=0;
    while (scanf("%d %d %d",&n,&m,&l)!=EOF)
    {
        cases++;
        for (int i=1;i<=m;i++)
            for (int j=1;j<=m;j++)
                dis[i][j]=0xffffff;
        for (int i=1;i<=n;i++)
            scanf("%d",&phone[i]);
        for (int i=1;i<=l;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            dis[a][b]=c;
            dis[b][a]=c;
        }
        int p;
        scanf("%d",&p);
        printf("Case #%d\n",cases);
        for (int s=1;s<=p;s++)
        {
            scanf("%d%d%d",&a,&b,&c);
            a=phone[a];
            b=phone[b];
            c=phone[c];
            dija();         //求a为源最短路
            dijb();         //求b为源最短路
            dijc();         //求c为源最短路
            int min=0xffffff;
            for (int i=1;i<=m;i++)//枚举中心点
            {
                if (disa[i]+disb[i]+disc[i]<min)
                    min=disa[i]+disb[i]+disc[i];
            }
            if (min!=0xffffff)
                printf("Line %d: The minimum cost for this line is %d.\n",s,min);
            else
                printf("Line %d: Impossible to connect!\n",s);
        }
    }
}