1 条题解

  • 0
    @ 2025-9-10 9:13:07

    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
    上传者