我用邻接链表做的。是不是有地方死循环了啊？
#include <iostream>
using namespace std;
__int64 vaule[100005];
struct node
{
	int num;
	node* next;
};
__int64 Abs(__int64 a)
{
	if(a>0)return a;
	else return -a;
}
node map[100005],*p,*sp,*v[100005],queue[999999];;
bool visit[100005];
bool vv[100005];
__int64 sum,Min;
void dfs(node*a)
{
	int flag;
	__int64 num;
	vv[a->num]=1;
	if(Min<num+num-sum)return ;
	num=vaule[a->num];
	flag=0;
	sp=a->next;
	for(;sp;)
	{
		if(flag==2)break;
		if(visit[sp->num]==0){flag++;}	
		if(visit[sp->num]==1)num+=vaule[sp->num];
		sp=sp->next;
	}
	if(flag<2)
	{
		visit[a->num]=1;
		vaule[a->num]=num;
		if(Abs(sum-num-num)<Min)Min=Abs(sum-num-num);
	}
	while(a->next)
	{
		if(visit[a->next->num]==1||vv[a->next->num])
		{
			a=a->next;
			continue;
		}
		dfs(&map[a->next->num]);
		vv[a->next->num]=0;
	}
}
int main ()
{
	int n,m,T,i,aa,bb,x;
	T=0;
	x=0;
	while(scanf("%d%d",&n,&m)&&(n||m))
	{
		memset(visit,0,sizeof(visit));
		memset(vv,0,sizeof(vv));
		T++;
		sum=0;
		for(i=1;i<=n;i++)
		{
			scanf("%I64d",&vaule[i]);
			sum+=vaule[i];
			map[i].num=i;
			map[i].next=NULL;
			v[i]=&map[i];
		}
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&aa,&bb);
			p=&queue[x++];
			p->num=bb;
			p->next=NULL;
			v[aa]->next=p;
			v[aa]=p;
			p=&queue[x++];
			p->num=aa;
			p->next=NULL;
			v[bb]->next=p;
			v[bb]=p;
		}
		Min=(__int64)1<<62;
		dfs(&map[1]);
		printf("Case %d: %I64d\n",T,Min);
	}
}

• Re:无语了、、、在杭电交3s的296ms过了，在这里就TLE了 (68) huxinjie800 2010-07-08 10:16:56