nyoj 677 碟战（dfs）

本是古典何须时尚 2024-02-17 21:05 17阅读 0赞

### 碟战 ###

时间限制： 2000 ms | 内存限制： 65535 KB

难度： 4

描述

知己知彼，百战不殆！在战争中如果被敌人掌握了自己的机密，失败是必然的。K国在一场战争中屡屡失败，就想到自己的某些城市可能会有敌方的间谍。

在仔细调查后，终于得知在哪些城市存在间谍。当然这个消息也被敌方间谍得知，所以间谍们开始撤离，试图到达K国唯一机场，然后抢夺飞机回国。由于城市内部比较复杂，K国领导人决定封锁道路，阻止所有间谍到达机场。城市编号为1~N，两个城市有不超过1条双向道路相连。机场在N号城市，不会有间碟。

由于要节约兵力，至少要封锁多少条道路才能阻止所有间谍到达机场？

输入

第一行包含一个整数T（T <= 100)，为测试数据组数。  
接下来每组测试数据第一行包含三个整数n,m,p（2<= n <= 200,1< m < 20000,1 <= p < n),分别表示城市数量，道路数量，存在间谍的城市的数量。  
接下来的一行包含p个整数x（1 <= x < n),表示存在间谍城市的编号。  
接下来的m行，每行包含两个整数i,j，表示城市i与城市j有道路相通。

输出

输出“Case \#i: ans”(不含引号),i为第i组数据，ans为需要封锁道路的条数。

样例输入

2
    4 4 2
    1 2
    1 2
    2 4
    1 3
    3 4
    4 3 2
    1 2
    2 3
    3 4
    2 4

样例输出

Case #1: 2
    Case #2: 2

分析：dfs就可以搜出来，几乎就是一个连通块问题的变形，用vector容器保存两点直接的关系，从某个间谍所在城市开始dfs搜索，对任意一个连通块，只要某一个分支到达城市n，那么道路数+1就行了。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<vector>
    using namespace std;
    const int maxn=200+2;
    vector<int>g[maxn];
    int P[maxn];  //保存间谍所在城市 
    int vis[maxn];
    int n,m,p;
    int cnt;
    
    void dfs(int cur){
    	if(cur==n){  //对于连通块来说，只要dfs搜索能到达n城市，需要封的道路数+1 
    		cnt++;
    		return ;
    	}
    	
    	vis[cur]=1;
    	
    	for(int i=0;i<g[cur].size();i++){
    		if(!vis[g[cur][i]]){
    			dfs(g[cur][i]);
    		}
    	}
    }
    int main(){
    	int T;
    	scanf("%d",&T);
    	int count=0;
    	while(T--){
    		scanf("%d%d%d",&n,&m,&p);
    		
    		for(int i=0;i<p;i++)
    		scanf("%d",&P[i]);
    		
    		for(int i=0;i<m;i++){
    			int a,b;
    			scanf("%d%d",&a,&b);
    			g[a].push_back(b);
    			g[b].push_back(a);
    		}
    		
    		cnt=0;
    		memset(vis,0,sizeof(vis));
    		for(int i=0;i<p;i++){
    			if(!vis[P[i]]){
    				dfs(P[i]);
    			}
    		}
    		
    		printf("Case #%d: %d\n",++count,cnt);
    		
    		for(int i=0;i<=n;i++)g[i].clear(); 
    	}
    	return 0;
    }