131 条题解
-
9
larryzhong LV 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
#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
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
FLOYED解决之。注意题目，只要是满足是在最短路上的点都可以计入答案。
http://hi.baidu.com/samroxas/item/18e3dcf260386b1ce2e3bd1f -
0
#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
#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
粗糙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
简单的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
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
貌似就我一个傻傻地用了bitset记录最短路点集⊙﹏⊙b
http://www.cnblogs.com/Onlynagesha/p/6965262.html -
0
编译通过...
├ 测试数据 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
zhangyq987 LV 8 @ 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
学了半年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
H2SO4HCLHNO3 LV 10 @ 2009-09-05 22:01:46
floyd
larryzhong
LV 9
@ 2017-04-27 13:24:23
