L2-025. 分而治之

時間限制600 ms
內(nèi)存限制65536 kB
代碼長度限制8000 B
判題程序Standard作者陳越

分而治之，各個擊破是兵家常用的策略之一。在戰(zhàn)爭中，我們希望首先攻下敵方的部分城市，使其剩余的城市變成孤立無援，然后再分頭各個擊破。為此參謀部提供了若干打擊方案。本題就請你編寫程序，判斷每個方案的可行性。

輸入格式：

輸入在第一行給出兩個正整數(shù) N 和 M（均不超過10 000），分別為敵方城市個數(shù)（于是默認城市從 1 到 N 編號）和連接兩城市的通路條數(shù)。隨后 M 行，每行給出一條通路所連接的兩個城市的編號，其間以一個空格分隔。在城市信息之后給出參謀部的系列方案，即一個正整數(shù) K （<= 100）和隨后的 K 行方案，每行按以下格式給出：

Np v[1] v[2] ... v[Np]

其中?Np?是該方案中計劃攻下的城市數(shù)量，后面的系列?v[i]?是計劃攻下的城市編號。

輸出格式：

對每一套方案，如果可行就輸出“YES”，否則輸出“NO”。

輸入樣例：10 11 8 7 6 8 4 5 8 4 8 1 1 2 1 4 9 8 9 1 1 10 2 4 5 4 10 3 8 4 6 6 1 7 5 4 9 3 1 8 4 2 2 8 7 9 8 7 6 5 4 2 輸出樣例：NO YES YES NO NO

第一反應(yīng)是要用并查集，可能是最近一直刷并查集的題目原因，一看到有路，求最后剩幾個的集合就是想到并查集。但是這題

并不那么的復(fù)雜，stl還是很好用的? ?有個find（）函數(shù)，查找快。

解析: 可以說，策略要滿足最后剩余的城市都是孤立的 ，比如3-4，所以我們這里可以先攻打3或者4其中一個，使其成為孤立的

按照這個思路，我們可以開一個二維數(shù)組，mp[][2],保存每一條路，最后在策略的基礎(chǔ)上遍歷一遍? 即可得出答案。

這里要說明一個? ?自己還是刷題不過? 感覺不夠，就像這里的find函數(shù)? ?就是自己太少用到，到比賽的時候就又自己花時間去寫

這個查找函數(shù)了? ?題目做多就會有這些的基礎(chǔ)。菜菜菜

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<list> #include<ctime> #include<algorithm> using namespace std;using namespace std; int mp[10005][2]; int main() { int n,m,t,p,q; cin>>n>>m; for(int i=1;i<=m;i++) cin>>mp[i][0]>>mp[i][1]; cin>>t; while(t--) { set<int>s; cin>>q; bool OK=1; for(int i=1;i<=q;i++) { cin>>p; s.insert(p);//存入方案城市 } for(int i=1;i<=m;i++) { if(s.find(mp[i][0])==s.end()&&s.find(mp[i][1])==s.end())//對于路兩端城市進行查找 //如果兩端都沒找到就令OK=0，循環(huán)退出 { OK=0; break; } } if(OK==0) cout<<"NO"<<endl; else cout<<"YES"<<endl; } }
與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的pat天梯赛L2-025. 分而治之的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。