首页 > 代码库 > POJ1985 DFS【STL__vector_的应用】

POJ1985 DFS【STL__vector_的应用】

2024-07-16 09:55:01   217人阅读

vector

    向量 相当于一个数组
    在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时，首先分配一个非常大的内存空间预备进行存储，即capacituy（）函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储，这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。
   优点：(1) 不指定一块内存大小的数组的连续存储，即可以像数组一样操作，但可以对此数组
               进行动态操作。通常体现在push_back() pop_back()
               (2) 随机访问方便，即支持[ ]操作符和vector.at()
               (3) 节省空间。
   缺点：(1) 在内部进行插入删除操作效率低。
               (2) 只能在vector的最后进行push和pop，不能在vector的头进行push和pop。
               (3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释
                     放 
 
这道题只需要双向DFS求个树的直径就可以了～
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <climits>#include <cstring>#include <stack>#include <vector>#include <algorithm>#define ll long longusing namespace std;const int INF = 0x3f3f3f3f;struct edge{    int ev,w;    edge(int a,int b):ev(a),w(b){ }};vector <edge> elist[400000];bool vis[400000];int s, ans;void DFS(int fv,int dis){    if (dis > ans){        ans = dis;        s = fv;    }    vis[fv] = true;    int size = elist[fv].size();    int ev,w;    for (int i = 0; i < size; ++i){        ev = elist[fv][i].ev;        w = elist[fv][i].w;        if (vis[ev]) continue;        DFS(ev,dis + w);    }}int main(){    int N,M;    int fv,ev,w;    char dir[10];    while(EOF != scanf("%d%d",&N,&M)){        for (int i = 1; i <= N; ++i)            elist[i].clear();        for (int i = 1; i <= M; ++i){            scanf("%d%d%d%s",&fv,&ev,&w,dir);            elist[fv].push_back(edge(ev,w));            elist[ev].push_back(edge(fv,w));        }        memset(vis,0,sizeof(vis));        s  = ans = 0;        DFS(1,0);        memset(vis,0,sizeof(vis));        ans = 0;        DFS(s,0);        printf("%d\n",ans);    }    return 0;}

 


联系
我们