POJ 1161 Walls【floyd 以面为点建图】

题目大意：

1.给出m个区域，n个俱乐部点。接下来是n个俱乐部点以及各个区域由什么点围成。求一个区域到各个俱乐部点的距离之和最小。

解题思路：

1.这题建图比较麻烦，以区域为点建图，区域之间若有边，则两区域的距离为1，建完图后跑一遍floyd就可以求出两两区域的最小距离。

2.对于答案，枚举每一个区域到各个俱乐部点的相邻区域的距离之和，取最小值。

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #define mem(a, b) memset(a, b, sizeof(a))

 using namespace std;

 const int inf = 0x3f3f3f3f;

 int m, n, l;

 int club[], vis[][];//标记i点是否与j区域相邻

 int edge[][]; //更新i到j边的相邻区域是哪个

 int map[][]; //建图

 void floyd()

 {

     for(int i = ; i <= m; i ++)

         map[i][i] = ;

     for(int k = ; k <= m; k ++)

         for(int i = ; i <= m; i ++)

             for(int j = ; j <= m; j ++)

                 map[i][j] = map[j][i] = min(map[i][j], map[i][k] + map[k][j]);

 }

 int main()

 {

     while(scanf("%d", &m) != EOF) //m个区域

     {

         mem(edge, -); //表示没有相邻区域

         mem(map, inf), mem(vis, -);

         scanf("%d%d", &n, &l);//n个点,其中l个点是俱乐部所在的点

         for(int i = ; i <= l; i ++)

             scanf("%d", &club[i]);

         for(int i = ; i <= m; i ++)

         {

             int k, temp;

             scanf("%d", &k); //每个区域由k个点逆时针围成 注意最后一个点与第一个点也有边

             scanf("%d", &temp);

             vis[temp][i] = ;

             int first = temp;

             for(int j = ; j < k; j ++)

             {

                 int x;

                 scanf("%d", &x);

                 vis[x][i] = ;

                 if(edge[temp][x] == - || edge[x][temp] == -)

                     edge[temp][x] = edge[x][temp] = i;

                 else

                 {

                     map[edge[temp][x]][i] = map[i][edge[temp][x]] = ;

                     edge[temp][x] = edge[x][temp] = i;

                 }

                 temp = x;

             }

             if(edge[first][temp] == - || edge[temp][first] == -)

                 edge[first][temp] = edge[temp][first] = i;

             else

             {

                 map[edge[first][temp]][i] = map[i][edge[first][temp]] = ;

                 edge[first][temp] = edge[temp][first] = i;

             }

         }

         floyd();

         int ans = inf;

         for(int i = ; i <= m; i ++) //枚举答案 枚举每一个区域

         {

             int temp = ;

             for(int j = ; j <= l; j ++)

             {

                 int temp1 = inf;

                 for(int k = ; k <= m; k ++)

                 {

                     if(vis[club[j]][k] == -)

                         continue;

                     temp1 = min(temp1, map[i][k]);

                 }

                 temp += temp1;

             }

             ans = min(ans, temp);

         }

         printf("%d\n", ans);

     }

     return ;

 }