1013 Battle Over Cities (25 分) java

论坛 期权论坛 编程之家     
选择匿名的用户   2021-6-2 20:57   2345   0

题意:

图问题,意思是在一个无向图中,以城市为顶点,城市之间有高速公路连接着,战争爆发,如果一个城市被敌人占领了,其他城市之间需要用高速公路运送物资,至少要修几条公路。


解题思路:

城市被占领后,本来连通(不一定)着的城市可能变得不再连通了,转化为求连通子图个数问题,即:这些城市之间形成了多少个连通子图(subConnectBranch:int),要把这些连通子图重新连接起来,至少要修subConnectBranch-1条公路。考虑到可能是个稀疏矩阵,于是采用邻接表建图。遍历领接表,每次遍历之前,重置vist[]数组,先把被占领的城市标记了,在未被占领的城市里,先将其标记,再用dfs遍历,如果dfs已完成,发现for循环里还有未标记的城市,还要再重新dfs一次,那么就说明已经产生了连通子图,于是更新subConnectBranch,使之++,直到所有城市均被标记,最后如果连通子图的值为1,则说明这个图除开被占领的城市后依然是连通的,那就不需要修了。个人觉得用bfs也可以达到同样的效果。但是不能ac,最后一个测试点始终超时,但思路感觉是没问题的,以后再用C/C++改写一下代码。


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
 public static void main(String[]args) throws IOException {
  
  BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
  String init[] = rd.readLine().split(" ");
  int n = Integer.parseInt(init[0]);
  int m = Integer.parseInt(init[1]);
  int k = Integer.parseInt(init[2]);
  City[] arr = new City[n+1];
  for(int i=1; i<arr.length; i++) {
   arr[i] = new City(i);
  }
  
  for(int i=0; i<m; i++) {
   String str[] = rd.readLine().split(" ");
   int x = Integer.parseInt(str[0]);
   int y = Integer.parseInt(str[1]);
   City p = arr[x];
   while(p.next != null) p = p.next;
   p.next = new City(y);
   City q = arr[y];
   while(q.next != null) q = q.next;
   q.next = new City(x);
  }
  
//  for(int i=1; i<n+1; i++) {
//   City p = arr[i];
//   System.out.print("city " + p.id + ": ");
//   while(p.next!=null) {
//    p = p.next;
//    System.out.print(p.id+" ");
//   }
//   System.out.println();
//  }
  String connect[] = rd.readLine().split(" ");
  for(int j=0; j<k; j++) {
   boolean visit[] = new boolean[n+1];
   int ocp = Integer.parseInt(connect[j]);
   visit[ocp] = true;
   int subConnectBranch = 0;
   for(int i=1; i<n+1; i++) {
    if(!visit[i]) {
     subConnectBranch++;
     visit[i] = true;
     dfs(visit, i, arr, ocp);
    }
   }
   System.out.println(subConnectBranch-1);
  }
 }
 public static void dfs(boolean visit[], int id, City[] arr, int ocp) {
  City p = arr[id];
  while(p.next != null) {
   p = p.next;
   if(p.id!=ocp && !visit[p.id]) {
    visit[p.id] = true;
    dfs(visit, p.id, arr, ocp);
   }
  }
 }
 static class City{
  int id;
  City next;
  public City(int id){
   this.id = id;
  }
 }
}


分享到 :
0 人收藏
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:3875789
帖子:775174
精华:0
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP