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

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

点击量：216

 

   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;
}

 

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback
bitcoin

… [Trackback]

[…] Read More to that Topic: wjyyy.top/524.html […]

赞0踩  回复
3 年 之前
wpdiscuz   wpDiscuz
更多阅读
标签云
DP gcd/lcm KMP LCA lct splay tarjan 二分答案 二进制 倍增 前缀和 区间DP 同余 图论 堆 字符串 学习笔记 平衡树 快速排序 拓扑排序 搜索 数列 数学 最小割 最短路 构造 枚举 树 树形DP 树状数组 树链剖分 概率期望 模拟 状态压缩 生成树 线段树 组合数学 网络流 背包 解题报告 计算几何 记录 贪心 递推 随笔
/* */