Menu
Article ACM

HDU 2874 Connections between cities

NodeKey

NodeKey

• 2 min read

换了个姿势还是上了HDU 据学长给我的图论题库来说 lca问题也写完了

这题几乎还是模板题 只不过是多了个 判断是否在同一棵树上 用了点小技巧 再Tarjan时 把根节点也传上去 如果得结果时根节点不同就跳过

另外这题灰常容易爆内存 稍微改了一下用 C++水过去了 然而G++还是爆………………

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>

using namespace std;
const int maxn=10005;
const int inf=0x3f3f3f3f;

struct node
{
    int v,d;
    node* nxt;
};

node *head1[maxn],edge1[maxn*2];
node *head2[maxn],edge2[2000002];
int root[maxn],ans[1000002],dis[maxn];
int vis[maxn];
int n,lnum,qnum,idx1,idx2;

void init()
{
    for(int i=0;i<=n;i++)
    {
        head1[i]=head2[i]=0;
        vis[i]=0;
    }
    idx1=idx2=0;
}

int fin(int x)
{
    if(root[x]==x) return x;
    return root[x]=fin(root[x]);
}

void add(int u,int v,int d,node *head[],node edge[],int& idx)
{
    edge[idx].v=v;
    edge[idx].d=d;
    edge[idx].nxt=head[u];
    head[u]=edge+idx++;

    edge[idx].v=u;
    edge[idx].d=d;
    edge[idx].nxt=head[v];
    head[v]=edge+idx++;
}

void Tarjan(int u,int rot)
{
    root[u]=u;
    vis[u]=rot;
    for(node* p=head2[u];p;p=p->nxt)
        if(vis[p->v]==rot)
            ans[p->d]=dis[u]+dis[p->v]-2*dis[fin(p->v)];
    for(node* p=head1[u];p;p=p->nxt)
        if(!vis[p->v])
        {
            dis[p->v]=dis[u]+p->d;
            Tarjan(p->v,rot);
            root[p->v]=u;
        }
}

int main()
{
    int u,v,d;
    while(scanf("%d%d%d",&n,&lnum,&qnum)!=EOF)
    {
        init();
        for(int i=1;i<=lnum;i++)
        {
            scanf("%d %d %d",&u,&v,&d);
            add(u,v,d,head1,edge1,idx1);
        }
        for(int i=1;i<=qnum;i++)
        {
            scanf("%d %d",&u,&v);
            ans[i]=inf;
            add(u,v,i,head2,edge2,idx2);
        }
        for(int i=1;i<=n;i++)
            if(!vis[i]) 
            {
                dis[i]=0;
                Tarjan(i,i);
            }
        for(int i=1;i<=qnum;i++)
        {
            if(ans[i]==inf) puts("Not connected");
            else printf("%d\n",ans[i]);
        }
    }
    return 0;
}
Share