131 条题解

  • 9
    @ 2017-04-27 13:24:23

    Floyd

    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    const int maxn = 110, INF = 0x3f3f3f3f;
    int dis[maxn][maxn];
    
    int print(int u, int v, int n) {
        int _count = 2;
        for (int i = 1; i <= n; i++)
            if (u != i && v != i && dis[u][v] == dis[u][i] + dis[i][v])
                _count++;
        return _count;
    }
    
    int main() {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i != j)
                    dis[i][j] = INF;
        while (m--) {
            int u, v;
            cin >> u >> v;
            dis[u][v] = dis[v][u] = 1;
        }
        // Floyd
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (i != j && j != k && i != k)
                        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        int q;
        cin >> q;
        while (q--) {
            int u, v;
            cin >> u >> v;
            cout << print(u, v, n) << endl;
        }
        return 0;
    }
    
  • 3
    @ 2017-05-30 17:21:00
    #include<stdio.h>
    #include<string.h>
    int n,m,p,s[1010][1010];
    int c(int x,int y,int z=0){
        for(int i=1;i<=n;++i) if(s[x][i]+s[i][y]==s[x][y]) z++;
        return z;
    }
    int main(){
        scanf("%d%d",&n,&m);
        memset(s,1,sizeof s);
        for(int i=1;i<=n;++i) s[i][i]=0;
        for(int x,y,i=0;i<m;++i){ 
            scanf("%d%d",&x,&y); 
            s[x][y]=1; s[y][x]=1;
        }
        for(int k=1;k<=n;++k)
            for(int i=1;i<=n;++i)
                for(int j=1;j<=n;++j)   
                    if(s[i][j]>s[i][k]+s[k][j]) s[i][j]=s[i][k]+s[k][j];
        scanf("%d",&p);
        for(int x,y,i=0;i<p;++i){
            scanf("%d%d",&x,&y);
            printf("%d\n",c(x,y));
        }
    }
    
  • 1
    @ 2018-08-11 11:09:06

    floyd
    ovo!!!

    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int f[110][110],n,m,a1,b1,a2,b2,ans,p;
    int ovo(int u,int v,int n1)
    {
        int sum=2;
        for(int i=1;i<=n;i++)
        {
            if(u!=i&&v!=i&&f[u][v]==f[u][i]+f[i][v])
            {
                sum++;
            }
        }
        return sum;
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i!=j)f[i][j]=0x3f;
            }
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a1,&b1);
            f[a1][b1]=1;
            f[b1][a1]=1;
        }
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(f[i][k]+f[k][j]<f[i][j])f[i][j]=f[i][k]+f[k][j];
                }
            }
        }
        scanf("%d",&p);
        for(int i=p;i>=1;i--)
        {
            scanf("%d%d",&a2,&b2);
            ans=ovo(a2,b2,n);
            printf("%d\n",ans);
        }
        return 0;
    * }
    
  • 1
    @ 2012-10-15 15:37:16

    FLOYED解决之。注意题目,只要是满足是在最短路上的点都可以计入答案。

    http://hi.baidu.com/samroxas/item/18e3dcf260386b1ce2e3bd1f

  • 0
    @ 2019-02-11 15:50:42

    #include<cmath>
    #include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    using namespace std;
    int n,m,a[101][101],p;
    int ans(int x,int y)
    {
    int q;
    q=0;
    for(int i=1;i<=n;i++)
    if(a[x][i]+a[i][y]==a[x][y])
    q++;
    return q;
    }
    int main()
    {
    int x,y;
    scanf("%d%d",&n,&m);
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=m;i++)
    {
    scanf("%d%d",&x,&y);
    a[x][y]=1;
    a[y][x]=1;
    }
    int i,j,k;
    for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(a[i][j]>a[i][k]+a[k][j])
    {
    a[i][j]=a[i][k]+a[k][j];
    }
    scanf("%d",&p);
    while(p--)
    {
    scanf("%d%d",&x,&y);
    printf("%d\n",ans(x,y)+2);

    }
    return 0;
    }

  • 0
    @ 2018-05-25 23:27:31
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    int edge[101][101];
    int n,m,a,b,sum;
    int find(int x,int y)
    {
        sum = 0;
        for(int i = 1; i<=n; i++)
            if(edge[x][i]+edge[i][y] == edge[x][y]) sum++;
        return sum;
    }
    int main()
    {
        memset(edge,27,sizeof(edge));
        cin>>n>>m;
        for(int i = 1; i <= m; i++)
            {
                cin>>a>>b;
                edge[a][b] = 1;
                edge[b][a] = 1;
    
            }
    
        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    if(edge[i][j]>edge[i][k]+edge[k][j])
                        edge[i][j]=edge[i][k]+edge[k][j];
        int q;
        cin>>q;
        for(int i = 1; i<=q; i++)
            {
    
                cin>>a>>b;
                cout<<find(a,b)+2<<endl;
            }
    
        return 0;
    }
    

    退役快一年了...

    竟然WA了半天
    忘记换行了...

  • 0
    @ 2017-11-05 21:05:42

    粗糙Floyd
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n,m,p;
    int g[108][108],f[108][108];
    void floyd()
    {
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(i!=j&&j!=k&&i!=k)
    g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    }
    int seach(int a,int b)
    {
    int ans=2;
    for(int i=1;i<=n;i++)
    {
    if(i!=a&&i!=b&&g[a][i]+g[i][b]==g[a][b])
    ans++;
    }
    return ans;
    }
    int main()
    {
    memset(g,0x7fffffff,sizeof(g));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(i!=j) g[i][j]=0x3f3f3f3f;
    for(int i=1;i<=m;i++)
    {
    int x,y;
    cin>>x>>y;
    g[x][y]=g[y][x]=1;
    }
    floyd();
    cin>>p;
    for(int i=1;i<=p;i++)
    {
    int a,b;
    cin>>a>>b;
    cout<<seach(a,b)<<endl;
    }
    return 0;
    }

  • 0
    @ 2017-11-04 20:27:42

    简单的Floyed (≖ ‿ ≖)✧

    #include<iostream>
    #include<cstring>
    #define INF 1000000
    using namespace std;
    int main()
    {
        int f[105][105];
        int n,m,a,b,p,num;
        cin>>n>>m;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(i==j)
                f[i][j]=0;
                else
                f[i][j]=INF;
            }
        }
        for(int i=1;i<=m;++i)
        {
            cin>>a>>b;
            f[a][b]=f[b][a]=1;
        }
        for(int k=1;k<=n;k++)
        {
            for (int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(f[i][k]+f[k][j]<f[i][j]&&i!=j&&i!=k&&j!=k)
                    {
                        f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
                    }
                }
            }
        }
        cin>>p;
        for(int i=1;i<=p;++i)
        {
            num=0;
            cin>>a>>b;
            for(int j=1;j<=n;++j)
            {
                if(f[a][b]==f[a][j]+f[j][b])
                num++;
            }
            cout<<num<<endl;
        }
        return 0;
    }
    
  • 0
    @ 2017-10-20 19:05:13

    floyd 两遍

    #include<stdio.h>
    #include<string.h>
    int n,m;
    int map[102][102];
    int ans[102][102];
    int main()
    {
        memset(map,0x3f,sizeof(map));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            map[x][y]=1;
            map[y][x]=1;
        }
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(map[i][k]+map[k][j]<map[i][j])
                    {
                        map[i][j]=map[i][k]+map[k][j];
                    }
                }
            }
        }
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(map[i][k]+map[k][j]==map[i][j])
                    {
                        ans[i][j]++;
                    }
                }
            }
        }
        int q;
        scanf("%d",&q);
        for(int i=1;i<=q;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",2+ans[x][y]);
        }
        return 0;
    }
    
    
  • 0
    @ 2017-06-08 23:16:27

    貌似就我一个傻傻地用了bitset记录最短路点集⊙﹏⊙b
    http://www.cnblogs.com/Onlynagesha/p/6965262.html

  • 0
    @ 2012-09-10 23:57:11

    水题面板编 连着WA四次。。。。

  • 0
    @ 2010-03-08 22:12:43

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    #include

    using namespace std;

    const int MAXN=10000000;

    const int N=101;

    int n,m,p;

    int f[N][N];

    int main(void)

    {

    int x,y;

    cin>>n>>m;

    for (int i=1;i>y;

    f[x][y]=f[y][x]=1;

    }

    cin>>p;

    for (int k=1;k>y;

    for (int k=1;k

  • 0
    @ 2009-11-04 22:45:16

    我还当就输出一条路上的总点数.就判定是样例错了..,.. 写了个Floyd就交了..全部wa

    可是是输出最短路上的总点数!!!多条最短路就得用中间点法求点的个数了!!!!!

  • 0
    @ 2009-10-27 23:57:38

    如果 map[a,b]=map[a,k]+map[k,b]

    那么 k 就是 a b 最短路上的点。

  • 0
    @ 2009-10-26 17:15:41

    の。看错题了。

  • 0
    @ 2009-10-25 22:07:29

    没什么好说的。。直接floyd。。

    输出的时候统计路上节点即可。。

    对于wa点的同志们。。小小的提个醒。。floyd枚举的顺序是

    for k:=1 to n do

    for i:=1 to n do

    for j:=1 to n do ...

  • 0
    @ 2009-10-24 18:44:22

    var

    bb:array[1..100]of boolean;

    f:array[1..100,1..100]of integer;

    path:array[1..100,1..100,0..100]of integer;

    i,j,k,m,n,p,a,b,ans,t:integer;

    procedure print(a,b:integer);

    var

    i:integer;

    begin

    if bb then

    begin

    inc(ans);

    bb:=false;

    end;

    if a=b then exit;

    for i:=1 to path[a,b,0] do

    print(a,path[a,b,i]);

    end;

    begin

    readln(n,m);

    fillchar(f,sizeof(f),127);

    fillchar(path,sizeof(path),0);

    for i:=1 to m do

    begin

    readln(a,b);

    f[a,b]:=1;f:=1;

    inc(path[a,b,0]);inc(path);

    path[a,b,1]:=a;path:=b;

    end;

    for k:=1 to n do

    for i:=1 to n do

    for j:=1 to n do

    if (f+f[k,j])

  • 0
    @ 2009-10-17 21:27:15

    学了半年Floyd还真没白学

    n=100不用Floyd做还真是天理不容

    就是注意一点 .. 答案要+2 (加上起点和终点两个点)

    program ex;var a:array[1..100,1..100] of longint ; n,m,p,i,j,x,y,ans:longint ;procedure floyd ;var i,j,k:longint ;begin for k := 1 to n do for i := 1 to n do for j := 1 to n do if (i j) and (j k) and (i k) then if a > a + a[k,j] then begin a := a + a[k,j] ; a[j,i] := a ; end ;end ;BEGIN read(n,m) ; for i := 1 to n do for j := 1 to n do a := maxint ; for i := 1 to m do begin read(x,y) ; a[x,y] := 1 ; a[y,x] := 1 ; end ; floyd ; read(p) ; for i := 1 to p do begin read(x,y) ; ans := 0 ; for j := 1 to n do if a[x,j] + a[j,y] = a[x,y] then inc(ans) ; writeln(ans + 2) ; end ;END .

  • 0
    @ 2009-09-10 17:27:19

    数据太弱了......

  • 0
    @ 2009-09-05 22:01:46

    floyd

信息

ID
1446
难度
5
分类
图结构 | 最短路 点击显示
标签
递交数
3499
已通过
1325
通过率
38%
被复制
9
上传者