1013.Battle Over Cities

2017-11-06

英文描述

Battle Over Cities (25)
It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair any other highways to keep the rest of the cities connected. Given the map of cities which have all the remaining highways marked, you are supposed to tell the number of highways need to be repaired, quickly.
For example, if we have 3 cities and 2 highways connecting city1-city2 and city1-city3. Then if city1 is occupied by the enemy, we must have 1 highway repaired, that is the highway city2-city3.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 3 numbers N (<1000), 0="" 1="" 2="" 3="" m="" and="" k,="" which="" are="" the="" total="" number="" of="" cities,="" remaining="" highways,="" cities="" to="" be="" checked,="" respectively.="" then="" lines="" follow,="" each="" describes="" a="" highway="" by="" integers,="" numbers="" connects.="" numbered="" from="" n.="" finally="" there="" is="" line="" containing="" k="" numbers,="" represent="" we="" concern.="" **output="" specification:**="" for="" output="" in="" highways="" need="" repaired="" if="" that="" city="" lost.="" **sample="" input:**="" output:**="" 0<="" font="">

中文描述

城市之战
一场战争中被铁路连接着的城市是相当重要的。如果一座城市被敌军占领，那么所有通向这座城市或者从这座城市开出的铁路都将被关闭。如果我们需要维修其他的铁路来保持剩下的城市之间的道路通畅。给出一个城市的地图，所有剩下的铁路将会被标记在地图中，你要，求得需要维修的铁路的条数。
举个例子。如果有3个城市2条铁路，城市1和城市2之间一条，城市1城市3之间一条。然后城市1被敌军占领了，我们就需要维修1条铁路，那就是城市2和城市3之间的铁路。
输入规格：
每一个输入文件包含一个测试用例。每个用例的第一行包含3个数字N（<1000），m和k，n是城市个个数，m是道路的个数，k就是被占领城市的个数。然后是m行，每行由2个整数组成，代表着铁路。城市被标号为1到n。最后是k个整数，代表着，如果那个城市被占领了，我们需求去维修多少条铁路。 0="" 1="" 2="" 3="" **输出规格：**="" 对于k个城市，在一行内输出那个城市失守后需求维修几条铁路才能保证剩下的城市保持连通。="" **样例输入:**="" **样例输出:**="" 0<="" font="">

分析与解题

当把题看明白后，就直接套用图论中遍历的算法就可以了。其实题意就是要求得一个图中有多少个联通子图。这个联通子图的概念我倒认为和树中的森林有相似之处，你也可以理解成一个深林中有多少棵树。然后你把题目那过来，他求得就是这些颗树木中需要多少条绳子把他们绑起来，他求得就是绳子的数量，当我们求得树木后在减去1也就是绳子数量，其实这儿题我倒认为有一点是不严谨的，他说求得是联通图，也可以保证每座城市间可以联通，但我求得的是强联通图，当然也能保证每座城市间相互连接。但题意要求得是联通图。
DFS在代码上写的最快，套上邻接矩阵，就会更快。其实主要是遍历的思想，算法实现上千变万化。代码写的不太优美，当时只是图快了

C语言实现

/*	DFS 写起来在代码是最少
*	刚读懂题意后，发现真的很简单
*	还有一点关于BFS和DFS一定要熟练
*/
#include<stdio.h>
int g[1000][1000] = {0};
int visited[1000] = {0};
int output[1000];
int n, m, k;
void input()
{
	int i, j;
	int c = 1;
	scanf("%d%d%d", &n, &m, &k);	
	while(c <= m)
	{
		scanf("%d%d", &i, &j);
		g[i][j] = g[j][i] = 1;
		c++;
	}
	c = 1;
	while(c <= k)
	{
		scanf("%d", &output[c]);
		c++;
	}
}
void dfs(int i)
{
	visited[i] = 1;
	int j = 1;
	while(j <= n)
	{
		if(g[i][j] == 1)
		{
			if(visited[j] == 0)
				dfs(j);
		}
		j++;
	}
}
void calc()
{
	int i = 1;
	int c;
	while(i <= k)
	{
		c = 0;
		int t = 1;
		while(t <= n)
		{
			visited[t] = 0;
			t++;
		}
		visited[output[i]] = 1;
		int j = 1;
		while(j <= n)
		{
			if(visited[j] == 0)
			{
				dfs(j);
				c++;
			}
			j++;
		}
		printf("%d\n", c - 1);
		i++;
	}
}
int main()
{
	input();
	calc();
	return 0;
}

测试链接

click me