nyoj-20-吝啬的国度(深搜)
生活随笔
收集整理的這篇文章主要介紹了
nyoj-20-吝啬的国度(深搜)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
吝嗇的國度
時間限制：1000?ms ?|? 內存限制：65535?KB 難度：3 描寫敘述每組測試數據的第一行輸入一個正整數N(1<=N<=100000)和一個正整數S(1<=S<=100000)。N表示城市的總個數，S表示參觀者所在城市的編號
隨后的N-1行。每行有兩個正整數a,b(1<=a,b<=N)，表示第a號城市和第b號城市之間有一條路連通。
（當中i=S時，請輸出-1）
解題思路：
? ? ? 一開始用了隊列來求，起點入隊。然后出隊。找到跟起點相連的城市進隊，那么這些城市的前一步就是出隊的城市了，然后開始不停地出隊入隊，直到隊空為止。思路不錯。可是超時了。
? ? ? 經過看大神的代碼，發現這個題能夠用深搜來解決，再一看題目發現這確實符合深搜的特性。
? ? ?無論是隊列還是深搜，都須要標記。
? ? ?隊列用到了#include<queue>STL函數，
#include <iostream> #include <queue> using namespace std; //這幾個頭文件不可缺少int main() { queue<類型（如int）> q; //使用前需定義一個queue變量，且定義時已經初始化 while(!q.empty()) q.pop(); //反復使用時，用這個初始化（空則返回1，不空返回0） q.push(1); //進隊列 q.pop(); //出隊列 int v=q.front(); //得到隊首的值 int s=q.size(); //得到隊列里元素個數return 0; }
? ? ? 由于給定的城市N的數目太大，建立數組須要用到#include<vector>，vector就是一個不定長數組，vector<int>a就是一個類似于int a[]的整數數組，僅僅只是他的長度不確定。能夠用a.size()讀取他的長度。
? ? ? 而vector<int>a[max]就是一個二維數組，僅僅是第一維的大小是固定的（不超過max），二維的大小就不固定了，這道題之所以用到vector就是利用了他的不定長，假設直接建立二維數組a[n][n]。n太大了，這種二維數組絕對超出內存。
? ? ??(1)頭文件#include<vector>.
? ? ? (2)創建vector對象，vector<int> vec;
? ? ? (3)尾部插入數字：vec.push_back(a);
? ? ? (4)使用下標訪問元素。cout<<vec[0]<<endl;記住下標是從0開始的。
? ? ? (5)向量大小:vec.size();
代碼：
//隊列思路（超時） #include<stdio.h> #include<string.h> #include<iostream> #include<queue> using namespace std; int sta[110000]; int map[110000][3]; int ans[110000]; int main() {int m;int n,s;int i,j,k;int now;queue<int>q;scanf("%d",&m);while(m--){scanf("%d%d",&n,&s);q.push(s);for(i=1;i<n;i++){map[i][0]=1;scanf("%d%d",&map[i][1],&map[i][2]);}memset(ans,0,sizeof(ans));ans[s]=-1;while(!q.empty()){now=q.front();q.pop();for(i=1;i<n;i++){if(map[i][0]&&map[i][1]==now){q.push(map[i][2]);ans[map[i][2]]=now;map[i][0]=0;}else if(map[i][0]&&map[i][2]==now){q.push(map[i][1]);ans[map[i][1]]=now;map[i][0]=0;}}}for(i=1;i<=n;i++){printf("%d",ans[i]);if(i!=n)printf(" ");elseprintf("\n");}}return 0; } //深搜代碼（AC） #include<stdio.h> #include<string.h> #include<iostream> #include<vector> #include<algorithm> using namespace std; int pre[100005]; vector<int>v[100005];void dfs(int s) {int i;for(i=0;i<v[s].size();i++){if(pre[v[s][i]])continue;pre[v[s][i]]=s;dfs(v[s][i]);} } int main() {int m;int n,s;int a,b;int i,j;scanf("%d",&m);while(m--){memset(v,0,sizeof(v));memset(pre,0,sizeof(pre));scanf("%d%d",&n,&s);pre[s]=-1;for(i=0;i<n-1;i++){scanf("%d%d",&a,&b);v[a].push_back(b);v[b].push_back(a);}dfs(s);for(i=1;i<=n;i++){printf("%d",pre[i]);if(i!=n)printf(" ");elseprintf("\n");}}return 0; }
轉載于:https://www.cnblogs.com/brucemengbm/p/6892334.html
總結
以上是生活随笔為你收集整理的nyoj-20-吝啬的国度(深搜)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [译] MDC-102 Flutter：
- 下一篇： Android 常用设计模式——观察者模