P2164 SHOI2007 交通网络

Itst · 2018-12-27 19:33:11 · 题解

题目还算不难吧

首先我们枚举点i，将其他所有点到这个点的最短路求出来

然后我们在这一次建出的最短路DAG的反图上进行拓扑排序。假设我们算到了点j，点j的人流量为t_j，点j连出去的边到达的点为点集\{v\}，那么对于每一个点u \in \{v\}，边(j,u)的流量就会增加\frac{t_j}{|\{v\}|}，t_u会加上\frac{t_j}{|\{v\}|}

总时间复杂度O(N^2)

强行插入自己的blog

#include<bits/stdc++.h>
#define ld long double
using namespace std;
inline int read(){
    int a = 0;
    char c = getchar();
    while(!isdigit(c))  c = getchar();
    while(isdigit(c))   a = (a << 3) + (a << 1) + (c ^ '0') , c = getchar();
    return a;
}
inline int max(int a , int b){
    return a > b ? a : b;
}
struct Ed{
    int start , end , upEd;
}ans[100001];
bool vis[301] , ifRail[301][301];
long long Times[301];
int firEd[301] , minRoute[301];
ld peo[301][301] , To[301][301];
struct cmp{
    bool operator() (const int& a, const int& b ){
        return minRoute[a] < minRoute[b];
    }
};
int main(){
    int N = read() , M = read();
    for(int i = 1 ; i <= M ; i++){
        int a = read() , b = read();
        ans[(i << 1) - 1].start = a;
        ans[(i << 1) - 1].end = b;
        ans[(i << 1) - 1].upEd = firEd[a];
        firEd[a] = (i << 1) - 1;
        ans[i << 1].start = b;
        ans[i << 1].end = a;
        ans[i << 1].upEd = firEd[b];
        firEd[b] = i << 1;
        ifRail[a][b] = ifRail[b][a] = 1;
    }
    for(int i = 1 ; i <= N ; i++)
        for(int j = 1 ; j <= N ; j++)   To[i][j] = read();
    for(int i = 1 ; i <= N ; i++){
        memset(minRoute , 0x3f , sizeof(minRoute));
        memset(Times , 0 , sizeof(Times));
        minRoute[i] = 0;
        Times[i] = 1;
        queue < int > q;
        priority_queue < int , vector < int > , cmp > q1;
        q.push(i);
        while(!q.empty()){
            int t = q.front();
            q.pop();
            bool f = 0;
            for(int j = firEd[t] ; j ; j = ans[j].upEd)
                if(minRoute[ans[j].end] > minRoute[t] + 1){
                    minRoute[ans[j].end] = minRoute[t] + 1;
                    Times[ans[j].end] = Times[t];
                    q.push(ans[j].end);
                    f = 1;
                }
                else    if(minRoute[ans[j].end] == minRoute[t] + 1){
                    Times[ans[j].end] += Times[t];
                    f = 1;
                }
            if(!f)  q1.push(t);
        }
        memset(vis , 0 , sizeof(vis));
        vis[i] = 1;
        while(!q1.empty()){
            int t = q1.top();
            q1.pop();
            for(int j = 1 ; j <= N ; j++)
                if(ifRail[j][t] && minRoute[j] == minRoute[t] - 1){
                    ld t1 = (ld)To[i][t] * Times[j] / Times[t];
                    peo[j][t] += t1;
                    peo[t][j] += t1;
                    To[i][j] += t1;
                    if(!vis[j]){
                        vis[j] = 1;
                        q1.push(j);
                    }
                }
        }
    }
    for(int i = 1 ; i <= M ; i++)
        cout << fixed << setprecision(1) << peo[ans[i << 1].start][ans[i << 1].end] + 1e-8 << endl;
    return 0;
}