Coder Space

题意：求一块空地i，使所有从俱乐部到i所翻越的城墙数最少。

构图：区域作为结点，两区域相邻，则用边连，构造图。最少翻越城墙的数目，即图论中最短路问题。

构图，即找出结点与结点间的相邻关系，即哪区域之间是用城墙隔开的。方法如下：
由于任何城墙只可能隔开两个区域，即任一城墙只可以出现在两块空地里，记录城墙出现的次数，记录两次则让两区域相邻。复杂度O(MN)。

因为俱乐部成员是在城市里，可以选择从城市周围的任一区域出发，所以要记录城市与哪些区域相连，计算路径时要选择相邻区域中到目的地的最短距离为俱乐部成员到目的地的最短距离。

算法过程：
（1）构造无向图。
（2）用Floyd算法求出任意两点间的最短路径。
（3）搜索每个区域，求俱乐部成员到该区域的距离和的最小值，即为结果。

  1#include<iostream>
  2#include<limits>
  3
  4using namespace std;
  5
  6const int maxM = 201;              //区域
  7const int maxN = 251;              //城市
  8const int maxL = 31;               //俱乐部
  9
 10const int INF = numeric_limits<int>::max();
 11
 12int mem[maxL];
 13int town[maxN][maxM];              //保存与城市i相邻的区域，其中town[i][0]用于计数
 14int walls[maxN][maxN];             //保存城墙，当一条城墙出现两次时，确定两区域相邻
 15int regions[maxM][maxM];           //区域邻接表
 16
 17int regTown[maxN];                 //临时存储区域的边城
 18
 19void Floyd(int n)
 20{
 21    for(int k=1;k<=n;k++)
 22    {
 23        for(int i=1; i<=n; i++)
 24        {
 25            for(int j=1; j<=n; j++)
 26            {
 27                if(regions[i][k] != INF && regions[k][j] != INF && (regions[i][k] + regions[k][j]) < regions[i][j])
 28                {
 29                    regions[i][j] = regions[i][k] + regions[k][j];
 30                }
 31            }
 32        }
 33    }
 34}
 35
 36//枚举每个区域，求最优区域
 37int Slove(int m,int nMem)
 38{
 39    int ans,cnt,minL;
 40    ans = INF;
 41    for(int i=1; i<=m; i++)
 42    {
 43        cnt = 0;
 44        for(int j=1; j<=nMem; j++)
 45        {
 46            int t = mem[j];
 47            minL = regions[i][town[t][1]];
 48            for(int k=2; k<=town[t][0]; k++)
 49            {
 50                if(regions[i][town[t][k]] < minL)
 51                {
 52                    minL = regions[i][town[t][k]];
 53                }
 54            }
 55            cnt += minL;
 56        }
 57        if(cnt < ans)
 58        {
 59            ans = cnt;
 60        }
 61    }
 62    return ans;
 63}
 64
 65int main()
 66{
 67    int M,N,L,I;
 68
 69    int i,j;
 70
 71    while(cin>>M)
 72    {
 73        cin>>N>>L;
 74
 75        //初始化计数
 76        for(i=1;i<=N;i++)
 77        {
 78            town[i][0] = 0;
 79            for(j=1; j<=N; j++)
 80            {
 81                walls[i][j] = 0;
 82            }
 83        }
 84
 85        for(i=1; i<=M; i++)
 86        {
 87            for(j=1; j<=M; j++)
 88            {
 89                regions[i][j] = INF;
 90            }
 91            regions[i][i] = 0;
 92        }
 93
 94        for(i=1; i<=L; i++)
 95        {
 96            cin>>mem[i];
 97        }
 98        for(i=1; i<=M; i++)
 99        {
100            cin>>I;
101            for(j=0;j<I;j++)
102            {
103                cin>>regTown[j];
104            }
105            regTown[I] = regTown[0];
106
107            //构造区域邻接图，记录城市的邻接区域
108            for(j=1; j<=I; j++)
109            {
110                town[regTown[j]][++town[regTown[j]][0]] = i;
111                if(walls[regTown[j-1]][regTown[j]] != 0)
112                {
113                    regions[i][walls[regTown[j-1]][regTown[j]]] = 1;
114                    regions[walls[regTown[j-1]][regTown[j]]][i] = 1;
115                }
116                else
117                {
118                    walls[regTown[j-1]][regTown[j]] = i;
119                    walls[regTown[j]][regTown[j-1]] = i;
120                }
121            }
122        }
123
124        Floyd(M);
125
126        cout<<Slove(M,L)<<endl;
127    }
128    return 0;
129}
130