poj3259Wormholes （Bellman_Ford/SPFA/Floyed算法判断是否存在负环）

时间：2024-05-13 18:04:08

题目链接：http://poj.org/problem?id=3259

题目大意：一个图，有n个顶点，其中有m条边是双向的且权值为为正，w条边是单向的且权值为负，判断途中是否存在负环，如果有输出YES，没有输出NO。

Sample Input

2

3 3 1

1 2 2

1 3 4

2 3 1

3 1 3

3 2 1

1 2 3

2 3 4

3 1 8

Sample Output

NO

YES

解题思路：套用Bellman_Ford算法判断图是否存在负环
具体详见代码：
#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int inf=0x3f3f3f3f;

int n,m,w,dist[],tot;

struct node{

    int from,to,d;

}edge[];

bool Bellman_Ford()

{

    for(int i=;i<=n;i++) dist[i]=inf;  //初始化

    dist[]=;

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

    {

        bool flag=;  //判断该轮是否可以松弛

        for(int j=;j<tot;j++)

        {

            if(dist[edge[j].to]>dist[edge[j].from]+edge[j].d)

            {  //进行松弛操作

                dist[edge[j].to]=dist[edge[j].from]+edge[j].d;

                flag=;

            }

        }

        if(flag) return false;  //当轮没有松弛表示没有负环

    }

    for(int i=;i<tot;i++)

    {

        if(dist[edge[i].to]>dist[edge[i].from]+edge[i].d)  //仍然可以松弛，表示有负环

        return true;

    }

    return false;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d%d",&n,&m,&w);

        tot=;

        for(int i=;i<=m;i++) //双向边

        {

            int a,b,c;

            scanf("%d%d%d",&a,&b,&c);

            edge[tot].from=a;

            edge[tot].to=b;

            edge[tot].d=c;

            tot++;

            edge[tot].from=b;

            edge[tot].to=a;

            edge[tot].d=c;

            tot++;

        }

        for(int i=;i<=w;i++)  //单向负边

        {

            scanf("%d%d%d",&edge[tot].from,&edge[tot].to,&edge[tot].d);

            edge[tot].d=-edge[tot].d;

            tot++;

        }

        if(Bellman_Ford())

            printf("YES\n");

        else

            printf("NO\n");

    }

    return ;

}

套用SPFA算法判断图是否存在负环

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<string>

#include<set>

#include<cmath>

#include<list>

#include<deque>

#include<cstdlib>

#include<bitset>

#include<stack>

#include<map>

#include<queue>

using namespace std;

typedef long long ll;

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

const double eps=1e-;

const ll mod=1e9+;

const int maxn=;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

const int dir[][]={{,},{-,},{,},{,-}};

ll n,m,p;

int head[maxn],vis[maxn],InQueue[maxn],dis[maxn];

int tot;

struct Edge{

    int to,w,next;

}edge[maxn*];

void Add_Edge(int u,int v,int w)

{

    edge[tot].to=v;

    edge[tot].w=w;

    edge[tot].next=head[u];

    head[u]=tot++;

}

bool spfa()

{

    queue<int> que;

    while(que.size())que.pop();

    que.push();

    vis[]=;

    InQueue[]++;

    dis[]=;

    while(que.size())

    {

        int u=que.front();

        que.pop();

        vis[u]=;

        for(int i=head[u];i!=-;i=edge[i].next)

        {

            int v=edge[i].to;

            if(dis[v]>dis[u]+edge[i].w)

            {

                dis[v]=dis[u]+edge[i].w;

                if(!vis[v])

                {

                    vis[v]=;

                    InQueue[v]++;

                    if(InQueue[v]>=n)return true;

                    que.push(v);

                }

            }

        }

    }

    return false;

}

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        tot=;

        cin>>n>>m>>p;

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

        {

            vis[i]=InQueue[i]=;

            dis[i]=INF;

            head[i]=-;

        }

        int u,v,w;

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

        {

            cin>>u>>v>>w;

            Add_Edge(u,v,w);

            Add_Edge(v,u,w);

        }

        for(int i=;i<p;i++)

        {

            cin>>u>>v>>w;

            w=-w;

            Add_Edge(u,v,w);

        }

        if(spfa()) puts("YES");

        else puts("NO");

    }

    return ;

}

Floyed算法判断负环：

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<string>

#include<set>

#include<cmath>

#include<list>

#include<deque>

#include<cstdlib>

#include<bitset>

#include<stack>

#include<map>

#include<queue>

using namespace std;

typedef long long ll;

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

const double eps=1e-;

const ll mod=1e9+;

const int maxn=;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

const int dir[][]={{,},{-,},{,},{,-}};

int n,m,p,mp[][];

bool Floyed()

{

    for(int k=;k<=n;k++)

    {

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

        {

            for(int j=;j<=n;j++)

            {

                if(mp[i][j]>mp[i][k]+mp[k][j])

                    mp[i][j]=mp[i][k]+mp[k][j];

            }

            if(mp[i][i]<)return true;

        }

    }

    return false;

}

int main()

{

    int T;

    cin>>T;

    while(T--)

    {

        cin>>n>>m>>p;

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

            for(int j=;j<=n;j++)

            {

                if(i==j)mp[i][j]=;

                else mp[i][j]=INF;

            }

        int u,v,w;

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

        {

            cin>>u>>v>>w;

            if(w<mp[u][v]) mp[u][v]=mp[v][u]=w;

        }

        for(int i=;i<p;i++)

        {

            cin>>u>>v>>w;

            mp[u][v]=-w;

        }

        if(Floyed())puts("YES");

        else puts("NO");

    }

    return ;

}

相关文章