Massive Algorithms: POJ 3259 -- Wormholes

POJ 3259 -- Wormholes

Description

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.
As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .
To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input

Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2..M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2..M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.

Output

Lines 1..F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).

Sample Input

Sample Output

NO
YES

英文理解起来有点累...很多农田,有的农田之间有路相连,从一个农田到另一个农田需要时间,然后有的农田中有虫洞,可以将你传送到另一个农场,并且时间会倒退..问FJ有没有可能在游历农场的过程中看到自己...

其实就是问有没有一个点,能在他从这个点出发前回到这个点,也就是求有没有负环.转了一圈后回到这个点时光倒退了,这样他在这个点等一会就能看到自己了..

求负环自然是Bellman-ford算法了..虫洞的边权为负值,为单向,但是农田之间路径是无向的.

POJ 3259 Wormholes 题解《挑战程序设计竞赛》

// 从顶点from指向顶点to的权值为cost的边

struct edge

{

    int from, to, cost;

    edge(){}

    edge(int from, int to, int cost)

{

        this->from = from;

        this->to = to;

        this->cost = cost;

}

};

// 边

edge es[MAX_E];

// 最短距离

int d[MAX_E];

// V是顶点数，E是边数

int V, E;

// 是否存在负圈

bool find_negative_loop()

{

    memset(d, 0, sizeof(d));

    for (int i = 0; i < V; ++i)

{

        for (int j = 0; j < E; ++j)

{

            edge e = es[j];

            if (d[e.to] > d[e.from] + e.cost)

{

                d[e.to] = d[e.from] + e.cost;

                // 如果更新了V次，则存在负圈

                if (i == V - 1)

{

                    return true;

}

}

}

}

    return false;

}

///////////////////////////SubMain//////////////////////////////////

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int F;

    cin >> F;

    while (F--)

{

        int N, M, W;

        cin >> N >> M >> W;

        V = N;

        E = 0;

        for (int i = 0; i < M; ++i)

{

            int from, to, cost;

            cin >> from >> to >> cost;

            --from;

            --to;

            es[E].from = from;

            es[E].to = to;

            es[E].cost = cost;

            ++E;

            // 无向图再来一次

              es[E].from = to;

              es[E].to = from;

              es[E].cost = cost;

              ++E;

}

        for (int i = 0; i < W; ++i)

{

            int from, to, cost;

            cin >> from >> to >> cost;

            --from;

            --to;

            es[E].from = from;

            es[E].to = to;

            es[E].cost = -cost;

            ++E;

}

        if (find_negative_loop())

{

            cout << "YES" << endl;

}

        else

{

            cout << "NO" << endl;

}

}

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

http://www.zrq495.com/poj-3259-wormholes/
bellman-ford算法代码：
Also check the code at http://blog.csdn.net/swm8023/article/details/6642634

7 int map[502][502];
 8 
 9 int bellman_ford(int n)
10 {
11     int dis[502], i, j, k;
12     for (i=1; i<=n; i++)
13         dis[i]=Max;
14     dis[1]=0;
15     int flag;
16     for (k=1; k<=n; k++)
17     {
18         flag=0;
19         for (i=1; i<=n; i++)
20         {
21             for (j=1; j<=n; j++)
22             {
23                 if (dis[j] > dis[i] + map[i][j])
24                 {
25                     dis[j]=dis[i]+map[i][j];
26                     flag=1;
27                 }
28             }
29         }
30         if (flag == 0)
31             return 0;
32         if (k == n)
33             return 1;
34     }
35 }
37 int main()
38 {
39     int a, b, d;
40     int T, n, m, w, i, j;
41     cin >> T;
42     while(T--)
43     {
44         cin >> n >> m >> w;
45         for (i=1; i<=n; i++)
46             for (j=1; j<=n; j++)
47                 map[i][j]=Max;
48         for (i=1; i<=m; i++)
49         {
50             cin >> a >> b >> d;
51             if (d < map[a][b])
52                 map[a][b]=map[b][a]=d;
53         }
54         for (i=1; i<=w; i++)
55         {
56             cin >> a >> b >> d;
57             if (-d < map[a][b])
58                 map[a][b]=-d;
59         }
60         if (bellman_ford(n))
61             cout << "YES" << endl;
62         else
63             cout << "NO" << endl;
64     }
65     return 0;
66 }

spfa算法代码：队列的数组开小了，一直RE。。。。也可以用循环队列。
http://twd2.me/index.php/archives/2608
Also check code at http://www.zrq495.com/poj-3259-wormholes/

class edge

{

    public:

        int v, ln;

        edge() : v(0), ln(0) {}

        edge(int v, int ln) : v(v), ln(ln) {}

};

int n,m,w;

vector<edge> G[600];

void init()

{

    cin>>n>>m>>w;

    for(int i=1;i<=n;++i)

{

        G[i].clear();

}

    int s,e,t;

    for(int i=1;i<=m;++i)

{

        cin>>s>>e>>t;

        G[s].push_back(edge(e,t));

        G[e].push_back(edge(s,t));

}

    for(int i=1;i<=w;++i)

{

        cin>>s>>e>>t;

        G[s].push_back(edge(e,-t));

}

}

bool SPFA()

{

    int ln[600],counter[600];

    bool inqueue[600];

    queue<int> Q;

    for(int i=1;i<=n;++i)

{

        ln[i]=0;

        Q.push(i);

        counter[i]=1;

        inqueue[i]=true;

}

    while(!Q.empty())

{

        int index=Q.front();

        Q.pop();

        inqueue[index]=false;

        for(vector<edge>::iterator it=G[index].begin();it<G[index].end();++it)

{

            if(ln[index]+it->ln<ln[it->v])

{

                ln[it->v]=ln[index]+it->ln;

                if(!inqueue[it->v])

{

                    Q.push(it->v);

                    ++counter[it->v];

                    inqueue[it->v]=true;

                    if(counter[it->v]>n-1)

                        return true;

}

}

}

}

    return false;

}

int main()

{

    int F;

    cin>>F;

    while(F--)

{

        init();

        cout<<(SPFA()?"YES":"NO")<<endl;

}

    return 0;

}

Read full article from 3259 -- Wormholes

POJ 3259 -- Wormholes

Labels

Popular Posts