1053. Path of Equal Weight (30)

原题链接：http://pat.zju.edu.cn/contests/pat-a-practise/1053
这道题目就是个树的遍历，反正树嘛可以好多方法构造的…我这边就给了个map实现，其实用数组也是完全可以的嘛:)
然后不管用DFS,BFS还是神马遍历一下整棵树就出来了…
能继续使用的在working里面，有结果的在result里面
一开始working集合放一个根节点的Path
注意特殊情况：只有根节点一个节点的时候….
其他没啥特别的，原以为10ms时间很短，做出来才发现其实都是0ms搞定的:)
另外另外，//掉的结构内的运算符重载，VS2013可以运行，但是PAT出现编译错误，貌似是linux下严格一些的吧，省事儿就改成了外面自定义比较函数了。据查，结构体内搞个友元函数然后结构体外面写实现也是可以的…不过这样好麻烦

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int *weight;
struct Path
{
    list path;
    long currWt;
    Path()
    {
        currWt = 0;
    }
    ////重载运算符实现sort
    //bool operator <(const Path& p2)
    //{
    //    list::const_iterator it1 = path.begin();
    //    list::const_iterator it2 = p2.path.begin();
    //    while(it1 != path.end() && it2 != p2.path.end())
    //    {
    //        int id1 = *it1;
    //        int wt1 = weight[id1];
    //        int id2 = *it2;
    //        int wt2 = weight[id2];
    //        if(wt2 > wt1)
    //            return false;
    //        else if(wt2 < wt1)
    //            return true;
    //        it1 ++;
    //        it2 ++;
    //    }
    //    return false;
    //}
};
bool compare (Path x, Path y)
{
    list::const_iterator it1 = x.path.begin();
        list::const_iterator it2 = y.path.begin();
        while(it1 != x.path.end() && it2 != y.path.end())
        {
            int id1 = *it1;
            int wt1 = weight[id1];
            int id2 = *it2;
            int wt2 = weight[id2];
            if(wt2 > wt1)
                return false;
            else if(wt2 < wt1)
                return true;
            it1 ++;
            it2 ++;
        }
        return false;
}
#define PAIR pair<int, vector>
int main()
{
    int N, M;
    long S;
    scanf("%d %d %ld", &N, &M, &S);
    weight = new int[N]; //weights
    bool *isLeaf = new bool[N];
    for(int i=0; i<N; i++)
        isLeaf[i] = true;
    map<int, vector> tree;
    vector results;
    vector working;
    for(int i=0; i<N; i++)
    {
        //read weight
        scanf("%d", &weight[i]);
    }
    for(int i=0; i<M; i++)
    {
        //read link info
        int nodeid;
        int K;
        scanf("%d %d", &nodeid, &K);
        isLeaf[nodeid] = false;
        vector linkedNodes;
        while(K--)
        {
            int dst;
            scanf("%d", &dst);
            linkedNodes.push_back(dst);
        }
        tree.insert(PAIR(nodeid, linkedNodes));
    }
    ///////////////////////////////
    //BFS root id = 00
    int wt_root = weight[0]; //根节点的权重
    Path path;
    path.currWt  = wt_root;
    path.path.push_back(0);
    working.push_back(path);
    while(!working.empty())
    {
        Path path = working.front(); //取最顶上一个操作
        int lastNode = path.path.back();
        int currWt = path.currWt; //当前的权重
        if(currWt == S)
        {
            //刚好了已经..(根节点就满足))
            results.push_back(path);
            working.erase(working.begin());
            continue;
        }
        vector linkedNodes = tree[lastNode];
        vector::iterator it;
        for(it = linkedNodes.begin(); it!=linkedNodes.end(); it++)
        {
            //遍历所有子节点
            int id = *it;
            int wt_till_this = weight[id] + currWt;//加上之后的权重
            if(wt_till_this > S)
                continue; //已经超过了
            else if(wt_till_this == S)
            {
                //刚好，加入result集合
                //如果还没到叶节点，那么它也不是答案!
                if(!isLeaf[id])
                    continue;
                Path newPath = path;
                newPath.currWt = wt_till_this;
                newPath.path.push_back(id);
                results.push_back(newPath);
            }
            else
            {
                //虽然还是小了，但是有希望
                Path newPath = path;
                newPath.currWt = wt_till_this;
                newPath.path.push_back(id);
                working.push_back(newPath);
            }
        }
        //使用完了之后，删掉这个
        working.erase(working.begin());
    }
    ///////////////////////////////
    //SORT
    sort(results.begin(), results.end(), compare);
    ///////////////////////////////
    //OUTPUT
    vector::iterator it;
    for(it = results.begin(); it != results.end(); it++)
    {
        Path p = *it;
        list::iterator iter;
        for(iter = p.path.begin(); iter != p.path.end(); iter++)
        {
            int id = *iter;
            int wt = weight[id];
            if(iter != p.path.begin())
                printf(" ");
            printf("%d", wt);
        }
        printf("n");
    }
    return 0;
}

Leave a Reply Cancel reply