1053. Path of Equal Weight (30)

2019-11-14 10:56:12

字体：大中小

来源：转载

供稿：网友

1053. Path of Equal Weight (30) 考察DFS

#include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;vector<vector<int>> path(1000);vector<vector<int>> v(200);vector<int> cur;int n,m,s,w[120];int cntw=0;bool comp(vector<int> &a,vector<int> &b){ auto ita=a.begin(); auto itb=b.begin(); while(ita!=a.end()&&itb!=b.end()&&(*ita)==(*itb)) { ++ita;++itb; } if(ita!=a.end()&&itb!=b.end()) return (*ita)>=(*itb); if(ita==a.end()&&itb!=b.end()) return false; else if(itb==b.end()&&ita!=a.end()) return true; else if(ita==a.end()&&itb!=b.end()) return true;}void DFS(int u){ cur.push_back(w[u]); cntw+=w[u]; if(!v[u].size()) { if(cntw==s) path.push_back(cur); //cout<<cntw<<endl; return; } for(auto it=v[u].begin();it!=v[u].end();++it) { DFS(*it); cntw-=cur.back(); cur.pop_back(); }}int main(){ cin>>n>>m>>s; for(int i=0;i!=n;++i) cin>>w[i]; for(int i=0;i!=m;++i) { int curid,temp,k; cin>>curid>>k; while(k--) { cin>>temp; v[curid].push_back(temp); } } DFS(0); sort(path.begin(),path.end(),comp); for(int i=0;i!=(int)path.size();++i) { for(auto it=path[i].begin();it!=path[i].end();++it) (it==path[i].end()-1)?cout<<*it<<endl:cout<<*it<<" "; } return 0;}

上一篇：13.1.6

下一篇：P1616 疯狂的采药