题解 P2850 【[USACO06DEC]虫洞Wormholes】

· · 题解

如果我们把每一条路权值看成通过所用的时间的话，那么我们便可以把虫洞的时间看成负权边，这样的话如果从一个点出发回到这个点所花的时间小于0，则说明虫洞起了作用回到了出发时间之前。

对于这个理解，我们可以看成负权环，如果我们枚举每一个点进行寻找是否存在负权环的话可能这道题能过，但是如果数据范围更大一点可能就会TLE了。

这个时候我们就可以采用超级源点的方法进行解决：

详情请看：超级源点和超级汇点的建立

<1>同时有多个源点和多个汇点，建立超级源点和超级汇点

<2>同时有多个源点和一个汇点，建立超级源点

<3>同时有多个汇点和一个源点，建立超级汇点

那么我们这里是要从多个地方进行寻找是否存在负变权，如果我们建立了超级源点，就只需要从超级源点开始进行找负权环，这样就可以自动找到是否存在负权环，省去了每一个点枚举一次找负权环的冗余操作，也就是<2>的情况。

对于超级源点，我们可以设置为0也可以设置为n+1，再将其与所有的图中的点相连，权值设为0（因为超级源点是一个模拟点，为了方便省时间，所以不存在，不可对整个图产生影响，故权值设为0）

接下来就是寻找负权环的操作，对于负权环，我们可以使用SPFA算法进行实现，因为如果出现负权边，对于SPFA的思想，他一定会一直围绕这条边不断进行松弛，则我们可以通过这个特性来判断负权环，而这个操作可以通过dfs的SPFA和bfs的SPFA进行。

如果对于dfs的SPFA，则就是在SPFA的松弛操作里， 如果新扩展的这个点之前已经扩展过了，就说明一条路中存在了两次这个点

那么就说明出现了环的情况。

部分代码如下

void pd(int x)
{
    if (flag)
    return ;
    b[x]=1;
    int k=h[x];
    while (k!=-1)
    {
        if (dis[a[k].to]>dis[x]+a[k].dis)
        {
            dis[a[k].to]=dis[x]+a[k].dis;
            if (b[a[k].to])
            {
                flag=1;  //标记出现负权环
                return ;
            }
            else
            pd(a[k].to);
        }
        k=a[k].next;
        }
    b[x]=0;
}

对于bfs的SPFA，我们可以利用这么一个思想：

如果对于一个有N个点的图，找到两个点存在最短路，那么他们经过的点一定小于等于n个点，那么如果我们到了当前这个点发现经过的点大于n个了，那么就说明一定存在环的情况了

部分代码如下：

while (!q.empty())
        {
            int x=q.front();
            q.pop();
            b[x]=0;
            int k=h[x];
            while (k!=-1)
            {
                if (dis[a[k].to]>dis[x]+a[k].dis)
                {
                    dis[a[k].to]=dis[x]+a[k].dis;
                    cnt[a[k].to]=cnt[x]+1;
                    if (cnt[a[k].to]>n)
                    {
                        flag=1;  //标记出现负权环
                        return ;
                        }
                    if(b[a[k].to]==0)
                    {
                        b[a[k].to]=1;
                        q.push(a[k].to);
                        } 
                    } 
                    k=a[k].next;
                }
            }

本题代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
struct CZP
{
    int next,to,dis;
}a[1000001];
int n,m,h[100001],b[100001],flag,t,top,dis[100001],w;
void cun(int from,int to,int dis)
{
    a[++top].next=h[from];
    a[top].to=to;
    a[top].dis=dis;
    h[from]=top;
}
void pd(int x)
{
    if (flag)
    return ;
    b[x]=1;
    int k=h[x];
    while (k!=-1)
    {
        if (dis[a[k].to]>dis[x]+a[k].dis)
        {
            dis[a[k].to]=dis[x]+a[k].dis;
            if (b[a[k].to])
            {
                flag=1;
                return ;
            }
            else
            pd(a[k].to);
        }
        k=a[k].next;
        }
    b[x]=0;
}   //这里使用了dfs的求负权环操作
int main()
{
    scanf("%d",&t);
    for (int k=1;k<=t;k++)
    {
        flag=0;
        scanf("%d%d%d",&n,&m,&w);
        for (int i=0;i<=n;i++)
        h[i]=-1;
        for (int i=1;i<=m;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            cun(x,y,z);
            cun(y,x,z);
            }     //小路为双向边！
        for (int i=1;i<=w;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            cun(x,y,-z);
        }   //虫洞改为负权值
        memset(b,0,sizeof(b));
        for (int i=1;i<=n;i++)
        cun(0,i,0);  //建立超级源点0
        for (int i=1;i<=n;i++)
        dis[i]=100000000;
        dis[0]=0;
        b[0]=1;
        pd(0);  
        if (flag==1)
        printf("YES\n");
        else
        printf("NO\n");
    }
    return 0;
}
*/