Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
森林,鉴定完毕,邻接表也可以做,对每个树做一遍就行!#include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <map> #define N 10000 #define M 100000 using namespace std; map<int,int> mp; int head[N],to[M],next[M],a[N],b[N],cnt,num,n,m,tc[N],dp[N][2]; bool vis[N]; inline void add(int u,int v) { to[cnt]=v; next[cnt]=head[u]; head[u]=cnt++; } void read() { mp.clear(); memset(head,-1,sizeof head);cnt=0; num=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) scanf("%d",&b[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) for(int k=1;k<=m;k++) if(abs(a[i]-a[j])==b[k]) { if(mp[a[i]]==0) {mp[a[i]]=++num;tc[num]=a[i];} if(mp[a[j]]==0) {mp[a[j]]=++num;tc[num]=a[j];} int ta=mp[a[i]],tb=mp[a[j]]; add(ta,tb),add(tb,ta); } } void find(int u,int fa) { vis[u]=true; for(int i=head[u];~i;i=next[i]) if(to[i]!=fa) find(to[i],u); dp[u][1]=tc[u];dp[u][0]=0; for(int i=head[u];~i;i=next[i]) if(fa!=to[i]) { dp[u][0]+=max(dp[to[i]][1],dp[to[i]][0]); dp[u][1]+=dp[to[i]][0]; } } void go() { memset(dp,0x8f,sizeof dp); memset(vis,0,sizeof vis); int ans=0; for(int i=1;i<=num;i++) if(!vis[i]) { find(i,-1); ans+=max(dp[i][0],dp[i][1]); } printf("%d\n",ans); } int main() { while(scanf("%d%d",&n,&m),n||m) { read(); go(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator