对于算法题：分而治之。这种要怎么写？

  • Z时代
  • 2024-03-04
  • 分类：IT

分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。

输入格式
输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （≤ 100）和随后的 K 行方案，每行按以下格式给出：

Np v[1] v[2] ... v[Np]
其中 Np 是该方案中计划攻下的城市数量，后面的系列 v[i] 是计划攻下的城市编号。

回答：

用一个map(HashMap<Integer, LinkedList>)存储与每座城市相通的城市，一个map(代码中sizeMap)存储与每座城市相通的城市数。每毁灭一座城市就将该城市相邻的城市数变为0，并且将之前与其相邻的城市的相邻城市数减一。最后通过遍历这个map判断是否每座城市相通的城市数都为0。当然，每判断一次map都要还原，所以要一个数组用来还原sizemap。

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class hw03_1 {
  //超时
  //C++可通过
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int m = scanner.nextInt();
    HashMap<Integer, LinkedList> map = new HashMap<>();
    HashMap<Integer, Integer> sizeMap = new HashMap<>();
    for (int i = 0; i < n; i++) {
      map.put(i + 1, new LinkedList());
      sizeMap.put(i + 1, 0);
    }
    int a, b;
    for (int i = 0; i < m; i++) {
      a = scanner.nextInt();
      b = scanner.nextInt();
      map.get(a).add(b);
      map.get(b).add(a);
      sizeMap.put(a, sizeMap.get(a) + 1);
      sizeMap.put(b, sizeMap.get(b) + 1);
    }
    int[] ints = new int[sizeMap.size()];
    for (int i = 0; i < sizeMap.size(); i++) {
      ints[i] = sizeMap.get(i + 1);
    }
    int k = scanner.nextInt();
    for (int i = 0; i < k; i++) {
      int index = scanner.nextInt();
      for (int j = 0; j < index; j++) {
        int cc = scanner.nextInt();
        sizeMap.put(cc, 0);
        for (int f = 0; f< n; f++) {
          if (map.get(f + 1).contains(cc)) {
            sizeMap.put(f + 1, sizeMap.get(f + 1) - 1);
          }
      }
      }
      if (isSuccess(sizeMap)) {
        System.out.println("YES");
      } else {
        System.out.println("NO");
      }
      for (int j = 0; j < ints.length; j++) {
        sizeMap.put(j + 1, ints[j]);
      }
    }
  }
  public static boolean isSuccess(HashMap<Integer, Integer> sizeMap) {
    for (int i = 0; i < sizeMap.size(); i++) {
      if (sizeMap.get(i + 1) > 0) {
        return false;
      }
    }
    return true;
  }
}

以上是 对于算法题：分而治之。这种要怎么写？ 的全部内容， 来源链接： utcz.com/p/944336.html

回到顶部