Loading...

洛谷P1993 小K的农场

check评论:2 条 remove_red_eye浏览量:806 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-09

这是一道差分约束的裸题$\text{qwq}$

我们设$f[i]$代表第$i$个农场的农作物

对于条件$1$,$f[l]\geq f[r]+x$我们从$l$向$r$连一条长度为$x$的边,代表$l$至少比$r$多$x$

对于条件$2$,$f[l]\leq f[r]+x$即$f[r] \leq f[l]-x$我们从$r$向$l$连一条长度为$-x$的边,代表$r$至少比$l$多$-x$

对于条件三,只要给$l$到$r$和从$r$到$l$各自连一条长度为$0$的边即可

然后就是找正环,我们用$spfa$求出每个点进入队列的次数,如果大于了$n$就是有正环,就是$No$

然后你开心从最短路(弱化版)里复制一个$spfa$,然后开心的$TLE$

底下的$dalao$都会什么$dfs$版$spfa$,蒟蒻不会,但是对于这种图,我们有更好的方法,将$spfa$中的$queue$换成$priority\_queue$即可,跑的还飞快,而且在强化版的最短路也可以毫无压力的通过

这个方法叫什么名字呢,嗯,就叫$dijkspfa$(逃

上代码$\text{qwq}$

#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int next,to,dis;
}e[500010];
int head[100010],dis[100010],vis[100010],cnt,tot[100010];
int n,m;
void add(int u,int v,int dis)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].dis=dis;
    head[u]=cnt;
}
bool spfa()
{
    priority_queue<int> q;
    memset(dis,0x80,sizeof(dis));
    vis[0]=1;
    dis[0]=0;
    tot[0]=1;
    q.push(0);
    while(!q.empty())
    {
        int u=q.top();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]<dis[u]+e[i].dis)
            {
                dis[v]=dis[u]+e[i].dis;
                if(!vis[v])
                {
                    tot[v]=tot[u]+1;
                    q.push(v);
                    vis[v]=1;
                    if(tot[v]>n)
                    {
                        return 1;
                    }
                }
            }
        }
    }
    return 0;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        add(0,i,0);
    }
    for(int i=1;i<=m;i++)
    {
        int opt,l,r,x;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==3)
        {
            if(l==r)
            {
                continue;
            }
            add(l,r,0);
            add(r,l,0);
            continue;
        }
        scanf("%d",&x);
        if(l==r&&x!=0)
        {
            printf("No");
            return 0;
        }
        if(l==r)
        {
            continue;
        }
        if(opt==1)
        {
            add(l,r,x);
            continue;
        }
        add(r,l,-x);
    }
    if(spfa())
    {
        printf("No");
    }
    else
    {
        printf("Yes");
    }
}

已有 2 条评论

正在回复给  
去登陆?

   点击刷新验证码

    ZCDHJ
    2018 - 09 - 12 20 : 33

    堆优化spfa可能会被卡成指数级呀。。。

    duyh1114
    duyh1114
    2018 - 09 - 13 21 : 44

    dalao%%%

标签云

文章留名

duyh1114
duyh1114