Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

DFS水过

Posted by fnoi16wjhui at 2018-07-03 14:18:40 on Problem 1192
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 1100
using namespace std;
int n,data[N*10],num[N*10],dn[N],sa[N][N];
bool flag[N];
struct node{int x,y,c;};
node a[N];
int dfs(int s){
	flag[s]=false;
	int ans=0;
	for(int i=1;i<=dn[s];++i)
		if(flag[sa[s][i]])ans+=max(0,dfs(sa[s][i]));
	return ans+a[s].c;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
		if(i!=j and abs(a[j].x-a[i].x)+abs(a[j].y-a[i].y)==1) sa[i][++dn[i]]=j;
	int ans=0;
	for(int i=1;i<=n;++i) memset(flag,1,sizeof flag),ans=max(ans,dfs(i));
	printf("%d",ans);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator