分而治之，各個擊破是兵家常用的策略之一。在戰(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 #include <bits/stdc++.h> using namespace std; const int N=1e4+5; vector<int> g[N]; int vis[N];//vis=1說明被攻下 vis=0說明仍然存在 bool dfs(int t) {for(int i=0;i<g[t].size();i++){int j=g[t][i];if(!vis[j])//j城市仍存在 return true;//有連通 }return false;//無連通 } int main() {int n,m,k;cin>>n>>m;for(int i=0;i<m;i++){int x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}int np;cin>>k;while(k--){cin>>np;memset(vis,0,sizeof vis);//全部城市置為存在 vector<int>node(np);for(int i=0;i<np;i++){cin>>node[i];vis[node[i]]=1;}int flag=1;for(int i=1;i<=n;i++){if(!vis[i]&&dfs(i))//該點未被訪問且有連通 {flag=0;break;}}if(flag)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return 0; }

?

總結(jié)

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

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