首页 > 代码库 > HDU 1491 社交网络（最短路计数）

HDU 1491 社交网络（最短路计数）

2024-07-09 00:06:57   217人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1491

题意：给出一个联通的无向图，边有权值。定义I(v)如下，计算每个点的I值。


思路：（1）最简单的就是那个floyd了。。。g[i][j]记录最短路长度，f[i][j]记录个数，不多说了；

（2）下面说说我自己想出来的算法。。枚举s和t，计算每个点到s和t的最短路。。然后建立最短路树。。之后求s到t的最短路个数。。然后枚举删掉某个点再求最短路个数，则差值即为通过删掉点的最短路数目。。。求最短路数目用优先队列。。

 

struct node{    int u,v,w,next;}; node edges[N*N];int head[N],e; void Add(int u,int v,int w){    edges[e].u=u;    edges[e].v=v;    edges[e].w=w;    edges[e].next=head[u];    head[u]=e++;} node edges1[N*N];int head1[N],e1; void Add1(int u,int v,int w){    edges1[e1].u=u;    edges1[e1].v=v;    edges1[e1].w=w;    edges1[e1].next=head1[u];    head1[u]=e1++;} int n,m;double ans[N]; int dis1[N],dis2[N];int visit[N],T; void BFS(int s,int dis[]){    T++;    int i;    FOR1(i,n) dis[i]=INF;    dis[s]=0;    queue<int> Q;    Q.push(s);    int u,v,w;    while(!Q.empty())    {        u=Q.front();        Q.pop();                 visit[u]--;        for(i=head[u];i!=-1;i=edges[i].next)        {            v=edges[i].v;            w=edges[i].w;            if(dis[v]>dis[u]+w)            {                dis[v]=dis[u]+w;                if(visit[v]!=T)                {                    visit[v]=T;                    Q.push(v);                }            }        }    }} struct Node{    int u,dis;         Node(){}    Node(int _u,int _dis)    {        u=_u;        dis=_dis;    }         int operator<(const Node &a) const    {        return dis>a.dis;    }}; i64 cnt[N]; i64 cal(int s,int t,int x){    priority_queue<Node> Q;    Q.push(Node(s,0));    clr(cnt,0); cnt[s]=1;    Node p;    int u,v,w,i,L=dis1[t];    int h[N]={0};     while(!Q.empty())    {        p=Q.top();        Q.pop();                 u=p.u; h[u]=0;        for(i=head1[u];i!=-1;i=edges1[i].next)        {            v=edges1[i].v;            w=edges1[i].w;            if(v==x) continue;            if(p.dis+w+dis2[v]==L)            {                cnt[v]+=cnt[u];                if(!h[v]) h[v]=1,Q.push(Node(v,p.dis+w));            }        }    }    return cnt[t];} void deal(int s,int t){    BFS(s,dis1); BFS(t,dis2);    clr(head1,-1); e1=0;    int L=dis1[t],i,u,v,w;    int h[N]={0};    FOR0(i,e)    {        u=edges[i].u;        v=edges[i].v;        w=edges[i].w;        if(dis1[u]+dis2[v]+w==L)          {            Add1(u,v,w);            h[u]=h[v]=1;        }    }     i64 sum=cal(s,t,-1),temp;    FOR1(i,n)     {        if(i!=s&&i!=t&&h[i])        {            temp=sum-cal(s,t,i);            ans[i]+=2.0*temp/sum;        }    }} int main(){    clr(head,-1);     RD(n,m);    int i,u,v,w;    FOR1(i,m)    {        RD(u,v,w);        Add(u,v,w);        Add(v,u,w);    }    int j;    FOR1(i,n) FOR(j,i+1,n) deal(i,j);    FOR1(i,n) PR(ans[i]);}

 

 

 


联系
我们