首页 > ACM题库 > HDU-杭电 > HDU 3323-Security Center[解题报告]HOJ
2014
03-16

HDU 3323-Security Center[解题报告]HOJ

Security Center

问题描述 :

Recently, wyh had learned a lot of knowledge about attack others’ computers. Now, if he has a way to access someone’s computer, the computers those connected directly or indirectly will suddenly be broken. To avoid it happening, the government set several computers with “Security Center”. These computers can prevent wyh’s attack. So they are called anti-wyhs. What’s more, anti-wyhs can protect the computers those connect to them directly or indirectly from wyh’s dreadful attack. But anti-wyhs can’t connect to a computer indirectly through wyh’s computer.

Now, the government asks you how many computers have been attacked.

输入:

The input will start with a line giving the number of test cases, T.
The first line of each case contains three integers n (0<n<20000), m (0<m<50000) and c(0<=c<=n-1) meaning the number of the computers including wyh’s, the number of those computers connect directly and the number of anti-wyhs. The second line contains c+1 integers. The first integer is the ID number of wyh’s computer. The following integers are the ID numbers of anti-wyhs. The ID number is numbered from 0 to n-1. Then m lines follow. Each line contain two integers x, y. This means that the computer x and y are connected directly.

Note, if computer x connects to computer y, computer y also can connect to computer x.

输出:

The input will start with a line giving the number of test cases, T.
The first line of each case contains three integers n (0<n<20000), m (0<m<50000) and c(0<=c<=n-1) meaning the number of the computers including wyh’s, the number of those computers connect directly and the number of anti-wyhs. The second line contains c+1 integers. The first integer is the ID number of wyh’s computer. The following integers are the ID numbers of anti-wyhs. The ID number is numbered from 0 to n-1. Then m lines follow. Each line contain two integers x, y. This means that the computer x and y are connected directly.

Note, if computer x connects to computer y, computer y also can connect to computer x.

样例输入:

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

样例输出:

0

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<queue>
#include<vector>
#define MAX 22222
using namespace std;
vector<int>vt[MAX];
int vis[MAX];
int a;
int d[MAX];
int BFS(int n){
		queue<int> q;
		q.push(n);
		int cnt=0;
		while(!q.empty()){
			int now=q.front();
			for(int i=0;i<vt[now].size();i++){
				int to=vt[now][i];
				if(vis[to]==0){
					vis[to]=1;
					cnt++;
					q.push(to);
				}
			}
			q.pop();
		}
		return cnt;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		memset(vis,0,sizeof(vis));  
		int n,m,c;
		scanf("%d%d%d",&n,&m,&c);
		scanf("%d",&a);
                for(int i=0;i<n;i++)vt[i].clear();
		for(int i=0;i<c;i++){
			scanf("%d",&d[i]);
		}
		for(int i=0;i<m;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			vt[u].push_back(v);
                        vt[v].push_back(u);
		}
		vis[a]=1;
		for(int i=0;i<c;i++){
			vis[d[i]]=1;
				BFS(d[i]);
		}
		printf("%d\n",BFS(a));
		
	}
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  3. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  4. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环