首页 > ACM题库 > HDU-杭电 > HDU 3298-Contestants-DFS[解题报告]HOJ
2014
03-13

HDU 3298-Contestants-DFS[解题报告]HOJ

Contestants

问题描述 :

In the new ACM-ICPC Regional Contest, a special monitoring and submitting system will be set up, and students will be able to compete at their own universities. However there’s one problem. Due to the high cost of the new judging system, the organizing committee can only afford to set the system up such that there will be only one way to transfer information from one university to another without passing the same university twice. The contestants will be divided into two connected regions, and the difference between the total numbers of students from two regions should be minimized. Can you help the juries to find the minimum difference?

输入:

There are multiple test cases in the input file. Each test case starts with two integers N and M , (1<=N<=100000, 1<=M<=1000000) , the number of universities and the number of direct communication line set up by the committee, respectively. Universities are numbered from 1 to N . The next line has N integers; the Kth integer is equal to the number of students in university numbered K. The number of students in any university does not exceed 100000000. Each of the following M lines has two integers s , t , and describes a communication line connecting university s and university t . All communication lines of this new system are bidirectional.

N = 0, M = 0 indicates the end of input and should not be processed by your program.

输出:

There are multiple test cases in the input file. Each test case starts with two integers N and M , (1<=N<=100000, 1<=M<=1000000) , the number of universities and the number of direct communication line set up by the committee, respectively. Universities are numbered from 1 to N . The next line has N integers; the Kth integer is equal to the number of students in university numbered K. The number of students in any university does not exceed 100000000. Each of the following M lines has two integers s , t , and describes a communication line connecting university s and university t . All communication lines of this new system are bidirectional.

N = 0, M = 0 indicates the end of input and should not be processed by your program.

样例输入:

7 6 
1 1 1 1 1 1 1 
1 2 
2 7 
3 7 
4 6 
6 2 
5 7 
0 0

样例输出:

Case 1: 1

#include <cstdio>
#include <cstring>
typedef long long llong;
const int Max=100010,MaxE=100010;
struct Edge{
	int v;
	Edge *nxt;
};
int N,M,a[Max];
Edge *hd[Max],e[MaxE*2],*ne;
bool vst[Max];
llong S,ans;
llong abs(llong x){return x<0?-x:x;}
void insert(int u,int v){
	ne->v=v,ne->nxt=hd[u];
	hd[u]=ne++;
	ne->v=u,ne->nxt=hd[v];
	hd[v]=ne++;
}
llong dfs(int u){
	if(vst[u]) return 0;
	vst[u]=true;
	llong size=a[u];
	for(Edge *p=hd[u];p;p=p->nxt){
		size+=dfs(p->v);
	}
	if(abs(S-size*2)<ans) ans=abs(S-size*2);
	return size;
}
int main(){
	for(int cas=1;scanf("%d %d",&N,&M)==2;++cas){
		if(N==0 && M==0) break;
		S=0;
		for(int i=0;i<N;++i){
			scanf("%d",a+i);
			S+=a[i]; 
		}
		memset(hd,0,sizeof(hd[0])*N);
		ne=e;
		for(int i=0;i<M;++i){
			int u,v;
			scanf("%d %d",&u,&v);
			--u,--v;
			insert(u,v); 
		}
		ans=S;
		dfs(0);
		memset(vst,0,sizeof(vst[0])*N);
		printf("Case %d: %I64d\n",cas,ans); 
	}
	return 0;
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。