1 条题解
-
0
C++ :
/*其实这个题就是把点当成面来给了,对于某一个区域,把他当成一个点, 和他相邻的区域与他之间有一条权为1的边, */ #include<stdio.h> #include<string.h> #define Max 210 #define INF 10000000 #define M 210 #define N 260 bool map[M][M]; struct Area { int town; //在该区域边上城镇数 int turn[N]; //这些城镇依次是turn[n]; int f[N]; //f[i]记i是turn[n]的第f[i]个数 }area[M]; bool check(int x, int y) { int i, a, b, t; bool yes = 0; for(i = 0; i < area[y].town; i++){ a = area[y].turn[i]; b = area[y].turn[(i+1)%area[y].town]; if(area[x].f[a] != -1 && area[x].f[b] != -1) { t = area[x].f[a]-area[x].f[b]; if(t == -1 || t == 1 || t == area[x].town-1 || t == 1-area[x].town) { yes = 1; break; } } } return yes; } int A[Max][Max]; void Floyd(int n) { int i, j, k; for(i = 0; i < n; i++){ for(j = 0; j < n; j++){ if(i != j && !map[i][j]) A[i][j] = INF; else A[i][j] = map[i][j]; } } for(k = 0; k < n; k++){ for(i = 0; i < n; i++) for(j = 0; j < n; j++) if(A[i][j] > A[i][k]+A[k][j]) A[i][j] = A[i][k]+A[k][j]; } } int main() { int i, j, m, n, l, man[40]; int town[N][N], num[N]; //freopen("walls.in", "r", stdin); //freopen("walls.out", "w", stdout); scanf("%d", &m); scanf("%d", &n); scanf("%d", &l); for(i = 0; i < l; i++) scanf("%d", &man[i]); memset(map, 0, sizeof(map)); memset(num, 0, sizeof(num)); for(i = 0; i < m; i++){ scanf("%d", &area[i].town); memset(area[i].f, -1, sizeof(area[i].f)); for(j = 0; j < area[i].town; j++){ scanf("%d", &area[i].turn[j]); area[i].f[area[i].turn[j]] = j; town[area[i].turn[j]][num[area[i].turn[j]]] = i; num[area[i].turn[j]]++; } for(j = 0; j < i; j++) map[i][j] = map[j][i] = check(i, j); } Floyd(m); int minsum, sum, min, k; for(i = 0; i < m; i++){ sum = 0; for(j = 0; j < l; j++){ min = A[town[man[j]][0]][i]; for(k = 1; k < num[man[j]]; k++){ if(min > A[town[man[j]][k]][i]) min = A[town[man[j]][k]][i]; } sum += min; } if(!i) minsum = sum; else if(minsum > sum) minsum = sum; } printf("%d\n", minsum); // } return 0; }Pascal :
var an,i,j,k,l,n,m,x,y,z:longint; a,b:array[0..200,0..200]of longint; c:array[1..30]of longint; d:array[0..250,0..201]of longint; procedure qzd; begin z:=maxlongint; for i:=1 to m do begin x:=0; for j:=1 to l do begin y:=maxlongint; for k:=1 to d[c[j],0] do if a[d[c[j],k],i]<y then y:=a[d[c[j],k],i]; inc(x,y); end; if x<z then z:=x; end; write(z); end; procedure hjm; begin for k:=1 to m do for i:=1 to m do for j:=1 to m do if a[i,k]+a[k,j]<a[i,j] then a[i,j]:=a[i,k]+a[k,j]; end; procedure cz; begin readln(m); readln(n); readln(l); for i:=1 to l do read(c[i]); readln; for i:=0 to m do for j:=0 to m do a[i,j]:=1000; for i:=1 to m do begin readln(k); read(x,y); z:=x; if b[y,x]>0 then begin a[i,b[y,x]]:=1; a[b[y,x],i]:=1; end else b[x,y]:=i; inc(d[x,0]); d[x,d[x,0]]:=i; inc(d[y,0]); d[y,d[y,0]]:=i; for j:=3 to k do begin x:=y; read(y); if b[y,x]>0 then begin a[i,b[y,x]]:=1; a[b[y,x],i]:=1; end else b[x,y]:=i; inc(d[y,0]); d[y,d[y,0]]:=i; end; x:=y; y:=z; if b[y,x]>0 then begin a[i,b[y,x]]:=1; a[b[y,x],i]:=1; end else b[x,y]:=i; end; for i:=0 to m do a[i,i]:=0; end; begin cz; hjm; qzd; end.
- 1
信息
- ID
- 4217
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者