题解

25 条题解

  • 1
    @ 2020-11-06 21:19:08

    #include<bits/stdc++.h>
    #define INF 1e9
    #define N 109
    using namespace std;
    typedef long long ll;
    ll n,m,a,b,d[N][N],cnt[N][N];;// n,m,a,b,c,d[i][j],cnt[i][j]是长整数变量,代表点数,边数,输入用的三个变量,从i到j的最短路,从i到j的最短路数量
    double ans;
    int main(){
    freopen("socialnetwork.in","r",stdin);
    freopen("socialnetwork.out","w",stdout);
    cin>>n>>m;
    fill(d[0],d[0]+109*109,INF);
    for(ll i=1;i<=m;i++){
    cin>>a>>b;
    cin>>d[a][b];
    d[b][a]=d[a][b];
    cnt[a][b]=cnt[b][a]=1;

    }
    for(ll k=1;k<=n;k++){
    for(ll i=1;i<=n;i++){
    for(ll j=1;j<=n;j++){
    ll cost=d[i][k]+d[k][j];
    if(cost==d[i][j]){
    cnt[i][j]+=cnt[i][k]*cnt[k][j];
    }
    else if(cost<d[i][j]){
    cnt[i][j]=cnt[i][k]*cnt[k][j];
    d[i][j]=cost;
    }
    }
    }
    }
    for(ll v=1;v<=n;v++){
    ans=0;
    for(ll s=1;s<=n;s++)if(s!=v){
    for(ll t=1;t<=n;t++)if(s!=t&&v!=t){
    if(d[s][t]==d[s][v]+d[v][t]){
    ans+=1.*cnt[s][v]*cnt[v][t]/cnt[s][t];
    }
    }
    }
    cout<<fixed<<setprecision(3)<<ans<<endl;
    }
    return 0;
    }

  • 0
    @ 2016-07-16 11:07:13

    Floyd用起来不太顺手所以跑了N遍Dijkstra
    #include <cstdio>
    #include <cstring>
    #include <algorithm>

    typedef long long longint;

    const int maxN=105;
    const int inf=0x3f3f3f3f;

    int N,M;
    int adj[maxN][maxN];
    longint cnt[maxN][maxN];
    int dist[maxN][maxN];
    bool vis[maxN];

    void initGraph()
    {
    memset(adj,0x3f,sizeof(adj));
    memset(cnt,0,sizeof(cnt));
    memset(dist,0x3f,sizeof(dist));
    }

    void input()
    {
    initGraph();
    scanf("%d%d",&N,&M);
    int u,v,w;
    for(int i=1;i<=M;i++)
    {
    scanf("%d%d%d",&u,&v,&w);
    adj[u][v]=adj[v][u]=w;
    }
    }

    void initDijkstra(int st)
    {
    memset(vis,0,sizeof(vis));
    dist[st][st]=0;
    cnt[st][st]=1;
    }

    void dijkstra(int st)
    {
    initDijkstra(st);
    int cur=st;
    for(int i=1;i<N;i++)
    {
    vis[cur]=true;
    for(int j=1;j<=N;j++) if(!vis[j])
    {
    if(dist[st][cur]+adj[cur][j]<dist[st][j])
    {
    dist[st][j]=dist[st][cur]+adj[cur][j];
    cnt[st][j]=cnt[st][cur];
    }
    else if(dist[st][cur]+adj[cur][j]==dist[st][j])
    cnt[st][j]+=cnt[st][cur];
    }
    int minDist(inf);
    for(int j=1;j<=N;j++)
    if(!vis[j] && dist[st][j]<minDist)
    {
    cur=j;
    minDist=dist[st][j];
    }
    }
    }

    double calcI(int x)
    {
    double ans(0.0);
    for(int i=1;i<=N;i++)
    for(int j=1;j<=N;j++) if(i!=x && j!=x) {
    if(dist[i][x]+dist[x][j]==dist[i][j])
    ans+=(1.0*cnt[i][x]/cnt[i][j]*cnt[x][j]);
    }

    return ans;
    }

    void solve()
    {
    for(int i=1;i<=N;i++) dijkstra(i);
    for(int i=1;i<=N;i++) printf("%.3f\n",calcI(i));
    }

    int main()
    {
    input();
    solve();
    return 0;
    }

  • 0
    @ 2016-06-27 20:16:56

    Dijkstra都秒了……
    ```c++
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    #include<queue>
    using namespace std;
    const int maxn = 200;

    struct Ed
    {
    int from,to,dis;
    Ed(int a=0,int b=0,int c=0) : from(a),to(b),dis(c) {}
    };

    struct Po
    {
    int d,dis;
    Po(int a=0,int b=0): d(a),dis(b) {}
    bool operator< (const Po &a) const { return dis>a.dis || (dis==a.dis&&d>a.d); }
    };

    vector<Ed> edges;
    vector<int> G[maxn];
    int n,m,min_dis[maxn][maxn];
    bool done[maxn];
    double ans[maxn];
    long long int path_num[maxn][maxn];
    priority_queue<Po> q;

    void Dijkstra(int s)
    {
    memset(done,0,sizeof(done));
    while(!q.empty()) q.pop();
    min_dis[s][s]=0;
    path_num[s][s]=1;
    q.push(Po(s,0));

    while(!q.empty())
    {
    int now=(q.top()).d;q.pop();
    if(done[now]) continue;
    done[now]=true;

    for(int i=0;i<(int)G[now].size();i++)
    {
    Ed& e=edges[G[now][i]];
    if(min_dis[s][e.to]==min_dis[s][now]+e.dis)
    path_num[s][e.to]+=path_num[s][now];
    if(min_dis[s][e.to]>min_dis[s][now]+e.dis||min_dis[s][e.to]==-1)
    {
    min_dis[s][e.to]=min_dis[s][now]+e.dis;
    path_num[s][e.to]=path_num[s][now];
    q.push(Po(e.to,min_dis[s][e.to]));
    }
    }
    }
    }

    inline void add_edges(int a,int b,int dis)
    {
    edges.push_back(Ed(a,b,dis));
    edges.push_back(Ed(b,a,dis));
    int k=edges.size();
    G[a].push_back(k-2);
    G[b].push_back(k-1);
    }

    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    add_edges(a,b,c);
    }

    memset(min_dis,-1,sizeof(min_dis));
    for(int i=1;i<=n;i++)
    Dijkstra(i);

    /*int a,b;
    while(scanf("%d%d",&a,&b)&&a!=0&&b!=0)
    {
    printf("%d %lld\n",min_dis[a][b],path_num[a][b]);
    printf("%d %lld\n",min_dis[b][a],path_num[b][a]);
    }*/

    memset(ans,0,sizeof(ans));

    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++)
    if(i!=j&&i!=k&&j!=k&&min_dis[j][i]+min_dis[i][k]==min_dis[j][k])
    ans[i]+=(double)(path_num[j][i]*path_num[i][k])/(double)path_num[j][k];

    for(int i=1;i<=n;i++)
    printf("%.3lf\n",ans[i]);
    return 0;
    }

    /*Accepted, time = 75 ms, mem = 1232 KiB, score = 100*/
    ```

  • 0
    @ 2015-12-04 23:40:34

    测试数据 #0: Accepted, time = 0 ms, mem = 400 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 400 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 400 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 400 KiB, score = 10

    测试数据 #4: Accepted, time = 0 ms, mem = 396 KiB, score = 10

    测试数据 #5: Accepted, time = 15 ms, mem = 396 KiB, score = 10

    测试数据 #6: Accepted, time = 15 ms, mem = 400 KiB, score = 10

    测试数据 #7: Accepted, time = 15 ms, mem = 396 KiB, score = 10

    测试数据 #8: Accepted, time = 15 ms, mem = 400 KiB, score = 10

    测试数据 #9: Accepted, time = 0 ms, mem = 396 KiB, score = 10

    Accepted, time = 60 ms, mem = 400 KiB, score = 100

    代码

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>

    using namespace std;

    int dist[100 + 2][100 + 2];
    long long num[100 + 2][100 + 2];
    int n , m , a , b , c;
    double ans;

    int main()
    {
    cin >> n >> m;
    memset( dist , 1 , sizeof( dist ) );
    for( register int i = 1 ; i <= m ; i++ )
    {
    scanf( "%d %d %d" , &a , &b , &c );
    dist[a][b] = dist[b][a] = c;
    num[a][b] = num[b][a] = 1;
    }
    for( register int k = 1 ; k <= n ; k++ )
    for( register int i = 1 ; i <= n ; i++ )
    for( register int j = 1 ; j <= n ; j++ )
    if( dist[i][j] > dist[i][k] + dist[k][j] )
    {
    dist[i][j] = dist[i][k] + dist[k][j];
    num[i][j] = num[i][k] * num[k][j];
    }
    else if( dist[i][j] == dist[i][k] + dist[k][j] )
    num[i][j] += num[i][k] * num[k][j];
    for( register int i = 1 ; i <= n ; i++ ) num[i][i] = 0;
    for( register int k = 1 ; k <= n ; k++ )
    {
    ans = 0;
    for( register int i = 1 ; i <= n ; i++ )
    for( register int j = 1 ; j <= n ; j++ )
    if( num[i][j] > 0 && dist[i][j] == dist[i][k] + dist[k][j] )
    ans += ( double )num[i][k] * num[k][j] / num[i][j];
    printf( "%.3f\n" , ans );
    }
    return 0;
    }
    %lf就WA0了%f就AC了。。。

  • 0
    @ 2010-03-26 22:33:35

    这么水的题目。。。NOI2007。。。直接用两个O(N^3)的循环就解决了。。。

    第一次没用int64挂了。。。显示的居然是错误200。。。

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-10-19 23:32:11

    NOI可以用int64么?

  • 0
    @ 2009-10-03 18:33:47

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    没啥好说的

  • 0
    @ 2009-09-27 14:50:58

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    通过   66人

  • 0
    @ 2009-09-05 16:29:03

    FLOYD先求出dis。

    sum[i][j]表示i~j最短路数量,则

    sum[i][j]=sigma(sum[i][k]|dis[i][k]+map[k][j]=dis[i][j])

    然后用sum求出Cs,t(v)即可

  • 0
    @ 2009-08-03 14:12:35

    近乎裸的Floyd

    int64极度猥琐~

  • 0
    @ 2009-08-02 22:25:20

    很简单的题目~

    由于数据范围很小,用floyd即可,不过考虑此题的特殊性,需在floyd算法中做一些改动,还需运用加法原理和乘法原理,细心是最主要的~

    题目有点繁琐,大家耐心做哦~

  • 0
    @ 2009-07-28 15:57:54

    沙茶题,floyd

  • 0
    @ 2009-07-25 21:50:47

    我要自杀,Floyd都能写错……………………

    祈祷今年NOI能有这样的题目

  • 0
    @ 2009-07-25 17:07:10

    桥 神 最硬啊!!!!!!!!!!!!!!!!!

  • 0
    @ 2009-07-25 15:36:08

    很简单

    (不过要注意用int64)

    用 floyd 可以秒杀哦~~

  • 0
    @ 2009-07-25 15:08:13

    占个位置先!

  • 0
    @ 2009-07-25 14:23:03

    地下室2层

  • 0
    @ 2009-08-03 20:04:11

    极度猥琐~

    !!!!!!!!!!

  • 0
    @ 2009-07-25 13:46:55

    NOI前最后一题.

信息

ID
1591
难度
5
分类
图结构 | 最短路 点击显示
标签
递交数
748
已通过
235
通过率
31%
被复制
1
上传者