题解 - Vijos

9

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

!TNT! LV 8 @ 7 年前

#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

暗燚 LV 8 @ 6 年前

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

hsez_zyf LV 10 @ 12 年前

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

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

0

李文杰 LV 8 @ 6 年前

#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

A1pine LV 4 @ 6 年前

#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

yyyz108 LV 8 @ 7 年前

粗糙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

伊人 LV 8 @ 7 年前

简单的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

lbz888 LV 7 @ 7 年前

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

Orina_zju LV 8 @ 7 年前

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

0

神犇 LV 10 @ 12 年前

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

0

嗤克 LV 9 @ 15 年前

编译通过...

├ 测试数据 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

Plam_gxy LV 10 @ 15 年前

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

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

0

他在那里 LV 7 @ 15 年前

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

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

0

supersun LV 7 @ 15 年前

の。看错题了。

0

fenghao LV 10 @ 15 年前

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

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

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

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do ...

0

zhangyq987 LV 8 @ 15 年前

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

林小雅 LV 10 @ 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 rocedure 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

zhh1993 LV 10 @ 15 年前

数据太弱了......

0

H2SO4HCLHNO3 LV 10 @ 15 年前

floyd

题解

131 条题解

最短路上的统计

信息

状态

开发

支持

题解

131 条题解

最短路上的统计

信息

状态

开发

支持

还没有账户？

登录