思路

1013 Battle Over Cities (25 分)
题目就不抄了，思路翻译以一下就是：
给出若干个城市n，以及哪些城市之间有路，题目要求解决的是：选取其中k个城市，其中一个被占领时，与之相关的路全部报废，问重新连接这些k-1个城市，至少要修几条路。

从样例基本可以看出，这个图的问题，把图转为矩阵，解题思路就是回溯，有想法，但是代码只能部分通过：
想法思路：

其中3被占领与2基本一致
python代码编写

#甲级1013
n = 0
visit = [[False for i in range(1001)] for j in range(1001)]
mapin = [[0 for i in range(1001)] for j in range(1001)]
//回溯
def dfs(start):
    global n
    global mapin
    global visit
    visit[start] = True
    for i in range(1,n+1):
        if visit[i] == False and mapin[start][i]==1:
            dfs(i)
n,m,k= map(int,input().split())
for i in range(0,m):
    x,y = map(int,input().split())
    mapin[x][y] = mapin[y][x] = 1
# 数组分隔输入数字
a = []
str = input()
a = [int(i) for i in str.split()]
//判断是否查过了，没查过就回溯，修路
for ak in a:
    cnt = 0
    visit = [False for i in range(6)]
    visit[ak] = True
    for h in range(1,n+1):
        if visit[h] == False:
            dfs(h)
            cnt+=1
       //最后的路会多修一条，减去即可
    print(cnt-1)

但是最后的代码没有完全通过，以后有想法在改进一下呗（思路若有问题，务必提出）~

参考博客