题目链接:http://poj.org/problem?id=1161

题目大意:

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 ;
}

最新文章

  1. 使用野狗(Wilddog)云setValue写入数据
  2. ExtJs 3.0 动态生成 CheckBox
  3. iOS 多线程讲解2
  4. addChildViewController 与 addSubview
  5. 完美解决CTRL+空格不能切换中/英文输入法的问题
  6. 数据库采用多表连接查询,对应javaBean文件连接方式
  7. java 不寻常的问题 No bean named &amp;#39;sessionFactory&amp;#39; is defined 和 initialize a collection of role
  8. mysqldump导入导出mysql数据库
  9. Samba匿名用戶仅仅唯读访问
  10. 性能调优:mysql之left join
  11. Codeforces 719A 月亮
  12. 有关Java垃圾回收的几个问题
  13. kaili 安装中文输入法
  14. Asp.Net Core中Json序列化处理整理
  15. Marathon1.5以上版本配置
  16. burpsuite的使用(一)
  17. Java之spilt()函数,trim()函数
  18. HDU4185(KB10-G 二分图最大匹配)
  19. Scrum 5.0(继4.0)
  20. js中call与apply的区别以及使用~

热门文章

  1. mouseover([[data],fn])
  2. Laravel API Errors and Exceptions: How to Return Responses
  3. Vue 组件中锚点定位的问题
  4. vue编辑、新增弹框(引用外部页面)
  5. LibreOJ #110. 乘法逆元
  6. const char*p,char const*p,char *const p
  7. Mybatis 返回值 返回Map的为空的值
  8. XMLHttpRequest Level2 新功能
  9. Android与JS交互,json传参问题
  10. Windows Bat 之For 循环