poj3259 WormHoles Spfa || BellmanFord

cucumber — Tue, 05 Jul 2011 17:20:00 GMT

1) Bellman Ford��法找负环的应用.

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <deque>
using namespace std;

struct Node {
    int to;
    int weight;
    Node *next;
};

#define MAXFIELD (1000 + 10)
#define MAXPATH (2500 + 10)
#define MAXWORMHOLE (200 + 10)
Node nodeHead[MAXFIELD];
Node nodes[MAXPATH * 2 + MAXWORMHOLE];
int dis[MAXFIELD + 1];
bool isInQueue[MAXFIELD + 1];
int allocPos = 0;
Node *getNode() {
    return nodes + allocPos++;
}
void initGraph(int n) {
    allocPos = 0;
    int i = 0;
    for (i = 0; i < n; ++i) {
        nodeHead[i].next = NULL;
        dis[i] = 0;
    }
}
void addEdge(int from, int to, int timeNeed) {
    Node *newNode = getNode();
    newNode->next = nodeHead[from].next;
    newNode->to = to;
    newNode->weight = timeNeed;
    nodeHead[from].next = newNode;
}

int main() {
    int caseCount, fieldCount, pathCount, wormHoleCount;
    int i, j, from, to, timeNeed;
    scanf("%d", &caseCount);
    for (i = 0; i < caseCount; i++) {
        scanf("%d%d%d", &fieldCount, &pathCount, &wormHoleCount);
        initGraph(fieldCount + 1);
        for (j = 0; j < pathCount; j++) {
            scanf("%d%d%d", &from, &to, &timeNeed);
            addEdge(from, to, timeNeed);
            addEdge(to, from, timeNeed);
        }
        for (j = 0; j < wormHoleCount; ++j) {
            scanf("%d%d%d", &from, &to, &timeNeed);
            addEdge(from, to, -timeNeed);
        }

        // 关键: 按照题目的要�? 可以看出是找图中有没有负�?br />        // 引入一个超�U�点s, s能够到达��L��一个field, 但是没有��M��field能够到达s
        // 然后如果图中不存在负�? 则在�l�过fieldCount�ơ松�?我叫优化)以后,
        // ��没有办法��L��一个field节点的权值变��了, 而如果存在负�?
        // 则还能松�?优化.
        // �q�就是�ؓ(f��)什么初始化旉��要把所有的field都压入队�?
        deque<int> q;
        for (j = 1; j <= fieldCount; ++j) {
            q.push_back(j);
            isInQueue[j] = true;
        }
        bool answer = false;
        int round = 0;
        while (!q.empty()) {
            int n = q.size();
            for (j = 0; j < n; j++) {
                int u = q.front();
                q.pop_front();
                isInQueue[u] = false;
                Node *tra;
                for (tra = nodeHead[u].next; tra != NULL; tra = tra->next) {
                    int temp = tra->weight + dis[u];
                    if (temp < dis[tra->to]) {
                        dis[tra->to] = temp;
                        if (!isInQueue[tra->to]) {
                            q.push_back(tra->to);
                            isInQueue[tra->to] = true;
                        }
                    }
                }
            }
            round++;
            if (round > fieldCount) {
                answer = true;
                q.clear();
                break;
            }
        }

        if (answer) {
            puts("YES");
        }
        else {
            puts("NO");
        }
    }

    return 0;
}

cucumber 2011-07-06 01:20 发表评论

cucumber — Tue, 05 Jul 2011 16:58:00 GMT

Dijkstra 未优化版, ��法相对清晰:

// 关键1: 处理每个人的��C��{��
// 办法: 枚�D--假设某种�Ҏ(gu��)��是最省钱�?
// 则该�Ҏ(gu��)��中的所有交易者的��C��{��都会(x��)落在一个宽度�ؓ(f��)rankLimit的区�?br />// 于是可以枚�D�q�个区间:
// [ownerRank[1] - rankLimit, ownerRank] ~ [ownerRank[1], ownerRank + rankLimit]
// 于是�q�道题考察了最短�\的dijkstra��法与枚丄��l�合.
//
// 其中枚�D可行是需要考察其复杂度�?
// dijkstra��法的复杂度�? O(n * n), n��Ҏ(gu��)��?br />// 枚�D量�ؓ(f��) rankLimit + 1;
// 于是枚�D + dijkstra的算法复杂度�?nbsp;O(n * n) * (rankLimit + 1)

// 关键2: 由题意要联想到用最短�\, 而且是边权�ؓ(f��)正的最短�\
// 1) 以物品�ؓ(f��)图节�?br />// 2) 设i物品如果能用j物品以�h(hu��n)格m交换, 则边(i,j)的权��gؓ(f��)m
// 3) 设求得节�?到物品x的最短�\, 该最短�\的权值和为tw(total weight的羃�?,
//    则从物品x开始物物交换的所有方案中, 最节省的方案会(x��)耗费tw + price[x]的金�?br />//    而婚�C�最��需要的金币数就是所�?nbsp;1 <= x <= goodsCount �?
//    tw[1][x] + price[x]最��的那个. (tw[1][x]表示1到x的最短�\径权�?

// 优化1: 在dijkstra��法的代码部�? 需要对原点到节点的最��距��L��否已知作出判�?
// �q�个判断是用bool数组disKnown来判断的, ��费大量旉��.
// 可以优化为添加一个数�l? 用该数组保存最��距��L��知的节点的编�?
// 只处理数�l�中的节�?
#include <cstdio>
using namespace std;

struct Node {
    int to;
    int weight;
    Node *next;
};

#define INF (1 << 30)
#define MAXNODE (100 + 10)
#define MAXEDGE (MAXNODE * MAXNODE + 10)
Node nodeHead[MAXNODE + 1];
Node nodes[MAXEDGE];
int ownerRank[MAXNODE + 1];
int price[MAXNODE + 1];
int minWeight[MAXNODE + 1];
bool disKnown[MAXNODE + 1];

int allocPos = 0;
Node *getNode() {
    return nodes + allocPos++;
}
void initGraph(int n) {
    allocPos = 0;
    int i = 0;
    for (i = 0; i < n; ++i) {
        nodeHead[i].next = NULL;
        minWeight[i] = INF;
    }
}
void addEdge(int from, int to, int weight) {
    Node *newNode = getNode();
    newNode->next = nodeHead[from].next;
    newNode->to = to;
    newNode->weight = weight;
    nodeHead[from].next = newNode;
}

int main() {
    int rankLimit, goodsCount, substituteCount, subPrice, num, minPrice, minWei;
    int minWeiPos;
    int i, j, rankStart;
    scanf("%d%d", &rankLimit, &goodsCount);
    initGraph(goodsCount + 1);
    for (i = 1; i <= goodsCount; ++i) {
        scanf("%d%d%d", price + i, ownerRank + i, &substituteCount);
        for (j = 0; j < substituteCount; ++j) {
            scanf("%d%d", &num, &subPrice);
            addEdge(i, num, subPrice);
        }
    }

    minPrice = price[1];
    for (rankStart = ownerRank[1] - rankLimit; rankStart <= ownerRank[1]; rankStart++) {
        for (i = 1; i <= goodsCount; ++i) {
            minWeight[i] = INF;
            // 如果某个节点/商品拥有者的阶��C��不在[rankStart, rankStart + rankLimit]
            // 的范围内, ��׃��必考虑该节�?br />            if (ownerRank[i] < rankStart || ownerRank[i] > rankStart + rankLimit) {
                disKnown[i] = true;
            }
            else {
                disKnown[i] = false;
            }
        }

        disKnown[1] = false;
        minWeight[1] = 0;
        for (i = 1; i <= goodsCount; ++i) {
            minWei = INF;
            for (j = 1; j <= goodsCount; ++j) {
                if (!disKnown[j] && minWeight[j] < minWei) {
                    minWei = minWeight[j];
                    minWeiPos = j;
                }
            }
            disKnown[minWeiPos] = true;
            if (minWei + price[minWeiPos] < minPrice) {
                minPrice = minWei + price[minWeiPos];
            }
            for (Node *tra = nodeHead[minWeiPos].next; tra != NULL; tra = tra->next) {
                if (!disKnown[tra->to] &&
                        minWeight[tra->to] > minWeight[minWeiPos] + tra->weight ) {
                    minWeight[tra->to] = minWeight[minWeiPos] + tra->weight;
                }
            }
        }
    }
    printf("%d\n", minPrice);

    return 0;
}

优化�? 速度要快一�? 但是代码比较隄��, 对变量的命名让�h比较恼火:

#include <cstdio>
using namespace std;

struct Node {
    int to;
    int weight;
    Node *next;
};

#define INF (1 << 30)
#define MAXNODE (100 + 10)
#define MAXEDGE (MAXNODE * MAXNODE + 10)
Node nodeHead[MAXNODE + 1];
Node nodes[MAXEDGE];
int ownerRank[MAXNODE + 1];
int price[MAXNODE + 1];
int minWeight[MAXNODE + 1];
int distanceUnknown[MAXNODE + 1];
int distanceUnknownCount;
bool isDistanceKnown[MAXNODE + 1];

int allocPos = 0;
Node *getNode() {
    return nodes + allocPos++;
}
void initGraph(int n) {
    allocPos = 0;
    int i = 0;
    for (i = 0; i < n; ++i) {
        nodeHead[i].next = NULL;
        minWeight[i] = INF;
    }
}
void addEdge(int from, int to, int weight) {
    Node *newNode = getNode();
    newNode->next = nodeHead[from].next;
    newNode->to = to;
    newNode->weight = weight;
    nodeHead[from].next = newNode;
}

int main() {
    int rankLimit, goodsCount, substituteCount, subPrice, num, minPrice, minWei;
    int minWeiDisUnkPos;
    int i, j, from;
    scanf("%d%d", &rankLimit, &goodsCount);
    initGraph(goodsCount + 1);
    for (i = 1; i <= goodsCount; ++i) {
        scanf("%d%d%d", price + i, ownerRank + i, &substituteCount);
        for (j = 0; j < substituteCount; ++j) {
            scanf("%d%d", &num, &subPrice);
            addEdge(i, num, subPrice);
        }
    }

    minPrice = price[1];
    for (from = ownerRank[1] - rankLimit; from <= ownerRank[1]; from++) {
        for (i = 1; i <= goodsCount; ++i) {
            minWeight[i] = INF;
        }
        distanceUnknownCount = 0;
        for (i = 1; i <= goodsCount; ++i) {
            if (ownerRank[i] >= from && ownerRank[i] <= from + rankLimit) {
                distanceUnknown[distanceUnknownCount++] = i;
                isDistanceKnown[i] = false;
            }
            else {
                isDistanceKnown[i] = true;
            }
        }

        minWeight[1] = 0;
        isDistanceKnown[1] = false;
        int n = distanceUnknownCount;
        for (i = 0; i < n; ++i) {
            minWei = INF;
            for (j = 0; j < distanceUnknownCount; ++j) {
                if (minWeight[ distanceUnknown[j] ] < minWei) {
                    minWei = minWeight[ distanceUnknown[j] ];
                    minWeiDisUnkPos = j;
                }
            }
            if (minWei + price[ distanceUnknown[minWeiDisUnkPos] ] < minPrice) {
                minPrice = minWei + price[ distanceUnknown[minWeiDisUnkPos] ];
            }
            for (Node *tra = nodeHead[ distanceUnknown[minWeiDisUnkPos] ].next; tra != NULL; tra = tra->next) {
                if (!isDistanceKnown[tra->to] &&
                        minWeight[tra->to] > minWeight[ distanceUnknown[minWeiDisUnkPos] ] + tra->weight ) {
                    minWeight[tra->to] = minWeight[ distanceUnknown[minWeiDisUnkPos] ] + tra->weight;
                }
            }
            isDistanceKnown[ distanceUnknown[minWeiDisUnkPos] ] = true;
            distanceUnknown[minWeiDisUnkPos] = distanceUnknown[--distanceUnknownCount];
        }
    }
    printf("%d\n", minPrice);

    return 0;
}

cucumber 2011-07-06 00:58 发表评论

poj1860 Currency Exchange: spfa / Bellman Ford

cucumber — Mon, 04 Jul 2011 01:18:00 GMT

摘要: 1) 实质��是是确定图中是否存在正�?-沿着�q�个环一直走能够使环内节点的权值无限增�?2) 特点�? 每个边的权值是动态变化的, �q�点提醒我们适合用Bellman Ford��法来处�?SPFA实质上是Bellman Ford的优�? ��法思想是一��L(f��ng)��).SPFA��法: Code highlighting produced by Actipro CodeHighlighter (freeware... 阅读全文

cucumber 2011-07-04 09:18 发表评论

亚洲电影免费,国产一区二区电影在线观看,欧美黄色免费网站

poj3259 WormHoles Spfa || BellmanFord

poj1860 Currency Exchange: spfa / Bellman Ford