2011年7月6日

poj3259 WormHoles Spfa || BellmanFord

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);
        }


        
// 关键: 按照题目的要求, 可以看出是找图中有没有负环
        
// 引入一个超级点s, s能够到达任意一个field, 但是没有任何field能够到达s
        
// 然后如果图中不存在负环, 则在经过fieldCount次松弛(我叫优化)以后, 
        
// 就没有办法使任意一个field节点的权值变小了, 而如果存在负环, 
        
// 则还能松弛/优化.
        
// 这就是为什么初始化时需要把所有的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;
}

posted @ 2011-07-06 01:20 cucumber 阅读(328) | 评论 (0)编辑 收藏

poj1062 昂贵的婚礼

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

// 关键1: 处理每个人的地位等级
// 办法: 枚举--假设某种方案是最省钱的, 
// 则该方案中的所有交易者的地位等级都会落在一个宽度为rankLimit的区间
// 于是可以枚举这个区间: 
// [ownerRank[1] - rankLimit, ownerRank] ~ [ownerRank[1], ownerRank + rankLimit]
// 于是这道题考察了最短路的dijkstra算法与枚举的结合.
//
// 其中枚举可行是需要考察其复杂度的: 
// dijkstra算法的复杂度为: O(n * n), n为节点数目
// 枚举量为 rankLimit + 1;
// 于是枚举 + dijkstra的算法复杂度为 O(n * n) * (rankLimit + 1)


// 关键2: 由题意要联想到用最短路, 而且是边权为正的最短路
// 1) 以物品为图节点
// 2) 设i物品如果能用j物品以价格m交换, 则边(i,j)的权值为m
// 3) 设求得节点1到物品x的最短路, 该最短路的权值和为tw(total weight的缩写), 
//    则从物品x开始物物交换的所有方案中, 最节省的方案会耗费tw + price[x]的金钱
//    而婚礼最少需要的金币数就是所有 1 <= x <= goodsCount 中, 
//    tw[1][x] + price[x]最小的那个. (tw[1][x]表示1到x的最短路径权值)


// 优化1: 在dijkstra算法的代码部分, 需要对原点到节点的最小距离是否已知作出判断.
// 这个判断是用bool数组disKnown来判断的, 浪费大量时间.
// 可以优化为添加一个数组, 用该数组保存最小距离未知的节点的编号. 
// 只处理数组中的节点.
#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;
            // 如果某个节点/商品拥有者的阶级地位不在[rankStart, rankStart + rankLimit]
            // 的范围内, 就不必考虑该节点
            
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;
}



优化后, 速度要快一些, 但是代码比较难看, 对变量的命名让人比较恼火:

#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;
}


posted @ 2011-07-06 00:58 cucumber 阅读(332) | 评论 (0)编辑 收藏

2011年7月4日

poj1860 Currency Exchange: spfa / Bellman Ford

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

posted @ 2011-07-04 09:18 cucumber 阅读(318) | 评论 (0)编辑 收藏

仅列出标题  
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜