洛谷P1993 小K的农场 题解【图论】【负环】【差分约束】【随机水过】

作者: wjyyy 分类: 图论,差分约束,最短路,解题报告,负环,随机水过 发布时间: 2018-06-22 17:49

点击量:21

 

   SPFA判负环是可以优化很多的,把进队次数为n优化到进队2次。

 

题目描述

小K在MC里面建立很多很多的农场,总共n个,以至于他自己都忘记了每个农场中种植作物的具体数量了,他只记得一些含糊的信息(共m个),以下列三种形式描述:

  • 农场a比农场b至少多种植了c个单位的作物,
  • 农场a比农场b至多多种植了c个单位的作物,
  • 农场a与农场b种植的作物数一样多。

 

但是,由于小K的记忆有些偏差,所以他想要知道存不存在一种情况,使得农场的种植作物数量与他记忆中的所有信息吻合。

 

输入输出格式

输入格式:

第一行包括两个整数 n 和 m,分别表示农场数目和小 K 记忆中的信息数目。

 

接下来 m 行:

如果每行的第一个数是 1,接下来有 3 个整数 a,b,c,表示农场 a 比农场 b 至少多种植了 c 个单位的作物。

 

如果每行的第一个数是 2,接下来有 3 个整数 a,b,c,表示农场 a 比农场 b 至多多种植了 c 个单位的作物。

 

如果每行的第一个数是 3,接下来有 2 个整数 a,b,表示农场 a 种植的的数量和 b 一样多。

 

输出格式:

如果存在某种情况与小 K 的记忆吻合,输出“Yes”,否则输出“No”。

 

输入输出样例

输入样例#1:
3 3
3 1 2
1 1 3 1
2 2 3 2
输出样例#1:
Yes

说明

对于 100% 的数据保证:1 ≤ n,m,a,b,c ≤ 10000。

 

   这个题的差分约束色彩很明显,不过一眼可能看不出来,因为以前做过的差分是求目标两点之间的最值(利用最短路)。这里的不合法性是用“最短路判负环”或“最长路判正环”来做的,我做的方法是最短路判负环。

 

   差分约束构图:\(x_i-x_j\leq k \Rightarrow (i,j,k)\),即从i向j连一条有向边,边权为k。当不等号方向不同时,化为统一,建图即可。如果有负环,代表着\(x_a-x_b\leq u,x_b-x_c\leq v,x_c-x_a\leq w\),如果$u+v+w<0$,那么不等式不成立,也就是没有符合条件的情况,在图上的体现就是负环。

 

   因为这个图不一定连通,所以我们要枚举没有经过的出发点,来判负环。我第一次A这个题时,感觉这样枚举进队n次判负环会T(而且常数很大),于是随机撒点100次,脸白就过了。。。可以看我的负环学习笔记了解多种判负环的方式的异处,这篇博客的最后贴了最优判负环方法的代码,可以了解一下。

 

   对于双端队列优化的SPFA,枚举进队n次是可以卡过的(没开O2)。全裸SPFA肯定是不行的。。。

 

Code:随机撒点(mx#:56ms)

#include<cstdio>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<ctime>
using std::deque;
struct node//指针链表
{
    int n,v;
    node *nxt;
    node(int n,int v)
    {
        this->n=n;
        this->v=v;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[10100],*tail[10100];
int f[10100],n;

bool used[10100];
int cnt[10100];
void spfa(int x)//spfa
{
    deque<int> q;
    memset(used,0,sizeof(used));
    memset(f,0,sizeof(f));
    memset(cnt,0,sizeof(cnt));
    q.push_back(x);
    f[x]=0;
    cnt[x]=1;
    used[x]=true;
    while(!q.empty())
    {
        int k=q.front();
        q.pop_front();
        used[k]=false;
        node *p=&head[k];
        while(p->nxt!=NULL)
        {
            p=p->nxt;
            if(f[k]+p->v<f[p->n])
            {
                f[p->n]=f[k]+p->v;
                if(!used[p->n])
                {
                    used[p->n]=true;
                    if(q.empty()||f[p->n]<q.front())//spfa优化
                        q.push_front(p->n);
                    else
                        q.push_back(p->n);
                    cnt[p->n]++;
                    if(cnt[p->n]>n)//判断进队第n+1次
                    {
                        printf("No\n");
                        exit(0);
                    }
                }
            }
        }
    }

    return;
}
int main()
{
    int m,op,u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)
        tail[i]=&head[i];
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&op);
        switch(op)
        {
            case 1:
                scanf("%d%d%d",&u,&v,&w);//差分约束系统
                tail[v]->nxt=new node(u,-w);
                tail[v]=tail[v]->nxt;
                break;
            case 2:
                scanf("%d%d%d",&u,&v,&w);
                tail[u]->nxt=new node(v,w);
                tail[u]=tail[u]->nxt;
                break;
            default:
                scanf("%d%d",&u,&v);
                tail[u]->nxt=new node(v,0);
                tail[u]=tail[u]->nxt;
                tail[v]->nxt=new node(u,0);
                tail[v]=tail[v]->nxt;
        }
    }
    srand(time(0));//美妙的随机啊
    for(int i=1;i<=100;i++)
        spfa(rand()%n+1);

    puts("Yes");//如果没能排除掉负环,就输出yes
    return 0;
}

 

Code:(双端队列+朴素判环)(mx#:452ms)

#include<cstdio>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<ctime>
using std::deque;
struct node//指针链表
{
    int n,v;
    node *nxt;
    node(int n,int v)
    {
        this->n=n;
        this->v=v;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[10100],*tail[10100];
int f[10100],n;

bool used[10100];
int cnt[10100];
void spfa(int x)
{
    deque<int> q;
    memset(used,0,sizeof(used));
    memset(f,0,sizeof(f));

    q.push_back(x);
    f[x]=0;
    cnt[x]=1;
    used[x]=true;
    while(!q.empty())
    {
        int k=q.front();
        q.pop_front();
        used[k]=false;
        node *p=&head[k];
        while(p->nxt!=NULL)
        {
            p=p->nxt;
            if(f[k]+p->v<f[p->n])
            {
                f[p->n]=f[k]+p->v;
                if(!used[p->n])
                {
                    used[p->n]=true;
                    if(q.empty()||f[p->n]<q.front())//双端队列优化
                        q.push_front(p->n);
                    else
                        q.push_back(p->n);
                    cnt[p->n]++;
                    if(cnt[p->n]>n)
                    {
                        printf("No\n");
                        exit(0);
                    }
                }
            }
        }
    }

    return;
}
int main()
{
    memset(cnt,0,sizeof(cnt));
    int m,op,u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)
        tail[i]=&head[i];
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&op);
        switch(op)
        {
            case 1:
                scanf("%d%d%d",&u,&v,&w);//差分约束系统
                tail[v]->nxt=new node(u,-w);
                tail[v]=tail[v]->nxt;
                break;
            case 2:
                scanf("%d%d%d",&u,&v,&w);
                tail[u]->nxt=new node(v,w);
                tail[u]=tail[u]->nxt;
                break;
            default:
                scanf("%d%d",&u,&v);
                tail[u]->nxt=new node(v,0);
                tail[u]=tail[u]->nxt;
                tail[v]->nxt=new node(u,0);
                tail[v]=tail[v]->nxt;
        }
    }

    for(int i=0;i<=n;i++)
        if(!cnt[i])//没有进过的都要做一遍
            spfa(i);

    puts("Yes");//没有排除掉
    return 0;
}

 

Code:最优解法,bfs-SPFA(mx#:4ms常数可以更优)(请勿尝试一般SPFA写dfs)

#include<cstdio>//此方法只在判负环时优秀
#include<cstring>//目的为最短路的SPFA判负环要用其他方法(类似于这个的方法)优化
#include<cstdlib>
struct node
{
    int n,v;
    node *nxt;
    node(int n,int v)
    {
        this->n=n;
        this->v=v;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[10100],*tail[10100];
bool vis[10100],used[10100];
int f[10100];
void spfa(int x)
{
    used[x]=true;
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(f[p->n]>f[x]+p->v)
        {
            f[p->n]=f[x]+p->v;
            if(used[p->n])
            {
                puts("No");
                exit(0);
            }
            spfa(p->n);//dfs
        }
    }
    used[x]=false;
}
int main()
{
    memset(f,0x3f,sizeof(f));
    memset(vis,0,sizeof(vis));
    int n,m,op,u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)
        tail[i]=&head[i];
    while(m--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&u,&v,&w);
            tail[v]->nxt=new node(u,-w);
            tail[v]=tail[v]->nxt;
        }
        else if(op==2)
        {
            scanf("%d%d%d",&u,&v,&w);
            tail[u]->nxt=new node(v,w);
            tail[u]=tail[u]->nxt;
        }
        else
        {
            scanf("%d%d",&u,&v);
            tail[u]->nxt=new node(v,0);
            tail[u]=tail[u]->nxt;
            tail[v]->nxt=new node(u,0);
            tail[v]-tail[v]->nxt;
        }
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])
            spfa(i);
    puts("Yes");
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */