POJ 1161 Walls（Floyd ，建图）-白红宇

POJ 1161 Walls（Floyd ，建图）

阅读量：4686 次

发布时间：2019-06-09

本文共 2039 字，大约阅读时间需要 6 分钟。

题意：

给定n个城市，然后城市之间会有长城相连，长城之间会围成M个区域，有L个vip（每个vip会处于一个城市里）要找一个区域聚会，问一共最少跨越多少个长城。

分析：

其实这题难就难在建图，因为图中的点不再是城市，而是城市之间长城围成的区域，只要把区域提取出来，这题就是简单的Floyd了。

我们可以把每个区域的边先记录下来，然后有共边的就是相邻的区域， vip所在的城市都是vip的出发区域，枚举聚会区域，然后都可能的vip区域都求一次取最少值再求和即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 #include
                 
                  #define rep(i,a,b) for(int i = a; i < b; i++)#define _rep(i,a,b) for(int i = a; i <= b; i++)#define mem(a,n) memset(a,n,sizeof(a))#define fre(a) freopen(a,"r", stdin);typedef long long LL;using namespace std;int M, N, L;const int Max = 300, Max_v = 50;int viper[Max_v];int G[Max][Max];vector
                  
                    city[Max][Max]; // which city have u to v;vector
                   
                     vip_city[Max];int close_city[300000];int main(){ rep(i,0,Max) rep(j,0,Max) G[i][j] = (i == j ? 0 : 1e6); cin >> M >> N >> L; rep(i,0,L){ cin >> viper[i]; } _rep(i,1,M){ int p,k,cnt = 0; cin >> k; int point[Max]; rep(j,0,k){ cin >> p; rep(q,0,L) if(p == viper[q]) vip_city[viper[q]].push_back(i); //把vip可能所在的城市加入vip_city point[cnt++] = p; } rep(j,0,cnt){ int u = point[j], v = point[(j+1)%cnt];//在环上每两个相邻点就是一条边 city[u][v].push_back(i); city[v][u].push_back(i); } } _rep(i,1,N){ _rep(j,1,N){ if(i != j && city[i][j].size() > 1){ int cnt = 0; rep(k,0,city[i][j].size()){ close_city[cnt++] = city[i][j][k];//如果这条边有多于2个城市， 那么这些城市两两之间都是相邻城市 } rep(k,0,cnt){ rep(l,k+1,cnt){ int u = close_city[k], v = close_city[l]; G[u][v] = 1; G[v][u] = 1; } } } } } for(int k = 1; k <= M; k++){ for(int i = 1; i <= M; i++){ for(int j = 1; j <= M; j++){ if(G[i][k] + G[k][j] < G[i][j]){ G[i][j] = G[i][k] + G[k][j]; } } } } int ans = 1e9; _rep(pick, 1, M){ //枚举聚会区域 int t = 0; rep(i,0,L){ //枚举每个vip的可能区域 int v = viper[i]; int min_dis = 1e6; rep(j,0,vip_city[v].size()) { int in = vip_city[v][j]; min_dis = min(min_dis, G[in][pick]); } t += min_dis; } ans = min(t, ans); } cout << ans << "\n";}

转载于:https://www.cnblogs.com/Jadon97/p/8319293.html

你可能感兴趣的文章