POJ1985 DFS【STL__vector_的应用】

时间：2023-12-31 22:56:14

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默认分配的大小时要进行整体的重新分配、拷贝与释
                     放 

vector<int> s;  
定义一个空的vector对象，存储的是int类型的元素。

vector<int> s(n);
定义一个含有n个int元素的vector对象。
vector<int> s(first, last);  
定义一个vector对象，并从由迭代器first和last定义的序列[first, last)中复制初值。

vector的基本操作有：

s[i]
直接以下标方式访问容器中的元素。

s.front()
返回首元素。
s.back()
返回尾元素。

s.push_back(x)
向表尾插入元素x。
s.size()
返回表长。

s.empty()
当表空时，返回真，否则返回假。
s.pop_back()
删除表尾元素。

s.begin()
返回指向首元素的随机存取迭代器。
s.end()
返回指向尾元素的下一个位置的随机存取迭代器。

s.insert(it, x)
向迭代器it指向的元素前插入新元素val。
s.insert(it, n, x)
向迭代器it指向的元素前插入n个x。

s.insert(it, first, last)
将由迭代器first和last所指定的序列[first, last)插入到迭代器it指向的元素前面。
s.erase(it)
删除由迭代器it所指向的元素。

s.erase(first, last)
删除由迭代器first和last所指定的序列[first, last)。
s.reserve(n)
预分配缓冲空间，使存储空间至少可容纳n个元素。

s.resize(n)
改变序列的长度，超出的元素将会被删除，如果序列需要扩展（原空间小于n），元素默认值将填满扩展出的空间。
s.resize(n, val)
改变序列的长度，超出的元素将会被删除，如果序列需要扩展（原空间小于n），将用val填满扩展出的空间。

s.clear()
删除容器中的所有的元素。
s.swap(v)
将s与另一个vector对象v进行交换。

s.assign(first, last)
将序列替换成由迭代器first和last所指定的序列[first, last)。[first, last)不能是原序列中的一部分。
要注意的是，resize操作和clear操作都是对表的有效元素进行的操作，但并不一定会改变缓冲空间的大小。

另外，vector还有其他一些操作如反转、取反等，不再一下列举。

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 long

using namespace std;

const int INF = 0x3f3f3f3f;

struct edge{

    int ev,w;

    edge(int a,int b):ev(a),w(b){ }

};

vector <edge> elist[];

bool vis[];

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 = ; 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[];

    while(EOF != scanf("%d%d",&N,&M)){

        for (int i = ; i <= N; ++i)

            elist[i].clear();

        for (int i = ; 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,,sizeof(vis));

        s  = ans = ;

        DFS(,);

        memset(vis,,sizeof(vis));

        ans = ;

        DFS(s,);

        printf("%d\n",ans);

    }

    return ;

}

相关文章