131 条题解
-
0
ltlxksz LV 8 @ 2008-09-15 13:54:24
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 9ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：9msFloyd+DFS
-
0
cools_boys LV 4 @ 2008-09-15 13:45:41
第100个。。。。
交了两次。。。。
第一次测试数据，结果数组开成了5*5。。。。
0分。。
开5000*5000 100分。。。 -
0
LV 0 @ 2008-09-15 12:54:37
有点想07NOI day1的第一题...
-
0
Floyd+String
Remember: String is Strong!
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 56ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：56ms字符串虽然说效率低了点...但是比较直观\易理解...
总的是用弗洛伊德做...
用字符串记录点数...
比如输入 1 2 代表1\2有边..那么就存p[1,2]:='1|2|'
如果有2 5 这条边 那么存p[2,5]:='2|5|'
那么1\5的最短路的p就可以存为p[1,2]+p[2,5]即'1|2|2|5'...
弄到最后用个boolean数组去重即可...for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if (ij) and (jk) and (ki) then
if w+w[k,j] -
0
tracy-henry LV 10 @ 2008-09-15 09:56:45
spfa+集合
-
0
function count(x,y:longint):longint;
var
t,w,i,j,s:longint;
pro:array[1..100,0..100]of longint;
b:array[1..100]of longint;
a:array[1..200]of longint;procedure review(x:longint);
var
i,j:longint;
begin
for i:=1 to pro[x,0] do
if b[pro[x,i]]=0 then begin
inc(s);
b[pro[x,i]]:=1;
review(pro[x,i])
end;
end;begin
s:=1;
fillchar(b,sizeof(b),0);
fillchar(a,sizeof(a),0);
fillchar(pro,sizeof(pro),0);
t:=1;
w:=1;
a[t]:=x;
b[x]:=1;
while (tb[a[t]])) do begin {这行写成b[y]>b[t]}
for i:=1 to n do
if (g[a[t],i]=1) then
if b[i]=0 then begin
inc(w);
a[w]:=i;
b[i]:=b[a[t]]+1;
inc(pro);
pro[i,pro]:=a[t]
end else if b[i]=b[a[t]]+1 then begin
inc(pro);
pro[i,pro]:=a[t]
end;
inc(t)
end;
fillchar(b,sizeof(b),0);
review(y);
count:=s;end;
BFS+倒拉链
写错一行扣100分………………
while (tb[a[t]])) do begin {这行却写成了b[y]>b[t]} -
0
ljj5112898 LV 3 @ 2008-09-19 20:46:31
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms奶奶的，一开始数组开的是10*10！囧...咋写都能过，水！
-
-1
#include <bits/stdc++.h> using namespace std; int graph[105][105]; int dis[105][105], que[105][105]; int n, m; int main() { scanf("%d%d", &n, &m); memset(dis, 127/3, sizeof dis); memset(que, 0, sizeof que); memset(graph, 127/3, sizeof graph); for (int i = 1; i <= n; i++) dis[i][i] = graph[i][i] = 0; for (int i = 1; i <= m; i++) { int x, y; scanf("%d%d", &x, &y); graph[x][y] = graph[y][x] = 1; } for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dis[j][i] = dis[i][j] = min(dis[i][j], dis[i][k] + graph[k][j]); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) if (dis[i][k] + dis[k][j] == dis[i][j]) que[i][j]++; int q, x, y; scanf("%d", &q); for (int i = 1; i <= q; i++) { scanf("%d%d", &x, &y); printf("%d\n", que[x][y]); } return 0; } -
-1
#include <stdio.h> #include <string.h> int a[110][110]; int s1,s2,ask,c,d,n,m; int min(int a1,int a2) { if(a1<a2) return a1; else return a2; } void work(int p,int q) { int ans=2; for(int i=1;i<=n;i++) { if(i!=p&&i!=q&&a[p][i]+a[i][q]==a[p][q]) ans++; } printf("%d\n",ans); } int main() { memset(a,0x3f,sizeof(a)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) a[i][i]=0; for(int i=1;i<=m;i++) { scanf("%d%d",&c,&d); a[c][d]=a[d][c]=1; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][k]+a[k][j]<a[i][j]) a[i][j]=a[i][k]+a[k][j]; scanf("%d",&ask); while(ask--) { scanf("%d%d",&s1,&s2); work(s1,s2); } return 0; } -
-1
stevenzheng2002 LV 5 @ 2016-08-30 21:47:49
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int map[101][101];
int n,m,q;
int main(){
cin>>n>>m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i != j) map[i][j] = 9999;
else map[i][j] = 0;
for(int i = 1; i <= m; i++){
int a,b;
cin>>a>>b;
map[a][b] = 1;
map[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(map[i][k] + map[k][j] < map[i][j])
map[i][j] = map[i][k] + map[k][j];
cin>>q;
while (q--){
int a,b,ans=2;
cin>>a>>b;
for(int i=1;i<=n;i++)
if(i != a && i != b && map[a][i] + map[i][b] == map[a][b])
ans++;
cout<<ans<<endl;
}
return 0;
} -
-1
floyed+枚举
枚举每个点判断是否在最短路径中
是则答案加一
c++
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int map[101][101];
int n,m,q;
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (i!=j) map[i][j]=9999;
else map[i][j]=0;
for (int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
map[a][b] = 1;
map[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 (map[i][k] + map[k][j] < map[i][j])
map[i][j] = map[i][k] + map[k][j];
cin>>q;
while (q--)
{
int a,b,ans=2;
cin>>a>>b;
for (int i=1;i<=n;i++)
if (i != a && i != b && map[a][i] + map[i][b] == map[a][b])
ans++;
cout<<ans<<endl;
}
return 0;
} -
-1
{
n<=100 p<=5000矩阵存取 floyed预处理
判断即可( 枚举 每个点是否在它的最短路上 );
}var
n,m,q,x,y,ans,i,j,k:longint;
dis:array[0..110,0..110]of longint;function min(x,y:longint):longint;
begin
if x>y then exit(y) else
exit(x);
end;procedure floyd(n:longint);
var
i,j,k:longint;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
dis[i,j]:=min(dis[i,j],dis[i,k]+dis[k,j]);
end;procedure init;
var
i,j:longint;
begin
readln(n,m);
for i:=1 to n do
for j:=1 to n do if i<>j then dis[i,j]:=maxlongint>>2;
for i:=1 to m do
begin
readln(x,y);
dis[x,y]:=1; dis[y,x]:=1;
end;
floyd(n);
end;begin
init;
readln(q);
for i:=1 to q do
begin
readln(x,y);
ans:=0;
for k:=1 to n do
if dis[x,k]+dis[k,y]=dis[x,y] then inc(ans);
writeln(ans);
end;
end.
ltlxksz
LV 8
@ 2008-09-15 13:54:24
