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 on 2011-07-06 01:20 cucumber 阅读(389) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年7月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜