首页 > 代码库 > UVAlive4080_Warfare And Logistics

UVAlive4080_Warfare And Logistics

2024-07-13 12:22:04   216人阅读

给一个无向图，求出两个值，所有点到所有其他点的最短距离和，任意删除一条边后的这个值。

数据规模是100点1000边。

白书例题，不多说了直接对于每个点求出最短路树，对于每条边，如果它不是最短路树上的边，那么我们不需要对它进行最短路计算了，由于点数只有100，那么树上的边只有n-1，所以我们对于以每个点为源点的树，只需要重新计算n-1次最短路即可，每次计算复杂度为n*m，最终复杂度就是n*n*m*log()。个人觉得有点高，不过实际跑起来还是很快的。

注意有重边，要多加判断了。

 

 

召唤代码君：

 

 

#include <iostream>#include <cstdio>#include <cstring>#include <queue>#define maxn 2222typedef long long ll;using namespace std;struct heapnode{    ll D,U;    bool operator < (heapnode ND) const {        return D>ND.D;    }};ll inf=~0U>>2;ll to[maxn],c[maxn],next[maxn],first[maxn],edge;ll u[maxn],v[maxn],w[maxn],minlen[maxn][maxn],tim[maxn][maxn];ll dis[maxn],from[maxn],C[maxn],f[maxn][maxn];bool key[maxn],akey[maxn],done[maxn];ll n,m,L,ans,sum;void _init(){    edge=-1,sum=ans=0;    for (int i=1; i<=n; i++)    {        first[i]=-1,C[i]=0;        for (int j=1; j<=n; j++) minlen[i][j]=inf;        for (int j=1; j<=m; j++) f[i][j]=0;    }}void addedge(int U,int V,int W){    edge++;    to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge;    edge++;    to[edge]=U,c[edge]=W,next[edge]=first[V],first[V]=edge;}ll dijkstra(int S,int EG,ll Dis[],ll From[],bool Key[]){    priority_queue<heapnode> Q;    for (int i=1; i<=n || i<=m; i++)    {        if (i<=n) Dis[i]=inf,From[i]=-1,done[i]=false;        if (i<=m) Key[i]=false;    }    Dis[S]=0;    Q.push((heapnode){0,S});    while (!Q.empty())    {        heapnode ND=Q.top();        Q.pop();        int cur=ND.U;        if (done[cur]) continue;            else done[cur]=true;        if (From[cur]!=-1) Key[From[cur]/2+1]=true;        for (int i=first[cur]; i!=-1; i=next[i])            if (i!=EG+EG-2 && i!=EG+EG-1 && Dis[cur]+c[i]<Dis[to[i]])            {                Dis[to[i]]=Dis[cur]+c[i];                From[to[i]]=i;                Q.push((heapnode){Dis[to[i]],to[i]});            }    }    ll tot=0;    for (int i=1; i<=n; i++)        if (Dis[i]!=inf) tot+=Dis[i];            else tot+=L;    return tot;}int main(){    inf*=inf;    while (scanf("%lld%lld%lld",&n,&m,&L)!=EOF)    {        _init();        for (int i=1; i<=m; i++)        {            scanf("%lld%lld%lld",&u[i],&v[i],&w[i]);            addedge(u[i],v[i],w[i]);            if (w[i]<minlen[u[i]][v[i]]) minlen[u[i]][v[i]]=minlen[v[i]][u[i]]=w[i],tim[u[i]][v[i]]=tim[v[i]][u[i]]=1;                else if (w[i]==minlen[u[i]][v[i]]) tim[u[i]][v[i]]++,tim[v[i]][u[i]]++;        }        for (int i=1; i<=n; i++)        {            C[i]=dijkstra(i,m+1,dis,from,key);            ans+=C[i];            for (int j=1; j<=m; j++)                if (!key[j] || tim[u[j]][v[j]]>1 || minlen[u[j]][v[j]]!=w[j]) f[i][j]=C[i];                else f[i][j]=dijkstra(i,j,dis,from,akey);        }        for (int i=1; i<=m; i++)        {            ll tmp=0;            for (ll j=1; j<=n; j++) tmp+=f[j][i];            sum=max(sum,tmp);        }        printf("%lld %lld\n",ans,sum);    }    return 0;}


联系
我们