赞
踩
对每棵树进行拓扑排序,同一时间可以采摘的进行暴力即可,代码写得有点丑陋…
#include<iostream> #include<vector> #include<queue> using namespace std; #define ll long long int val[1005]; vector<int>ve[1005]; int indeg[1005]; queue<int>q1,q2; vector<int>ans; int main() { int n; scanf("%d",&n); for(int i=1;i<=2*n;i++) { scanf("%d",&val[i]); } for(int i=1;i<=2*n;i++) { int t; scanf("%d",&t); if(t==0)continue; ve[i].push_back(t); indeg[t]++; } for(int i=1;i<=n;i++) { if(indeg[i]==0)q1.push(i); } for(int i=n+1;i<=2*n;i++) { if(indeg[i]==0)q2.push(i); } for(int i=0;i<n;i++) { int ap=-1,pr=-1; int q1SIZE=q1.size(),q2SIZE=q2.size(); for(int j=0;j<q1SIZE;j++) { int apple=q1.front(); q1.pop(); for(int k=0;k<q2SIZE;k++) { int pear=q2.front(); q2.pop(); q2.push(pear); if(ap==-1) { ap=apple;pr=pear; } else if((val[apple]^val[pear])>(val[ap]^val[pr])) { ap=apple;pr=pear; } else if((val[apple]^val[pear])==(val[ap]^val[pr])) { if(val[apple]>val[ap]) { ap=apple;pr=pear; } else if(val[apple]==val[ap]) { if(apple>ap) { ap=apple;pr=pear; } else if(apple==ap) { if(pear>pr) { ap=apple,pr=pear; } } } } } q1.push(apple); } ans.push_back(val[ap]^val[pr]); for(int j=0;j<q1SIZE;j++) { int tmp=q1.front(); q1.pop(); if(tmp==ap) { for(int k=0;k<ve[tmp].size();k++) { indeg[ve[tmp][k]]--; if(indeg[ve[tmp][k]]==0) { q1.push(ve[tmp][k]); } } } else { q1.push(tmp); } } for(int j=0;j<q2SIZE;j++) { int tmp=q2.front(); q2.pop(); if(tmp==pr) { for(int k=0;k<ve[tmp].size();k++) { indeg[ve[tmp][k]]--; if(indeg[ve[tmp][k]]==0) { q2.push(ve[tmp][k]); } } } else { q2.push(tmp); } } } for(int i=0;i<n;i++) { if(i!=n-1)cout<<ans[i]<<" "; else cout<<ans[i]<<'\n'; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。