P1993 题解

· · 题解

题目传送门

诶诶诶怎么一个题解都没有，那么让我水一发吧。

SF 在讨论里说卡 DFS-DPFA，反正我用差分约束水，嘿嘿嘿。

差分约束入门？

现在来看看这道题。

题目说：

  1. 农场 a 比农场 b 至少多种植了 c 个单位的作物；

  2. 农场 a 比农场 b 至多多种植了 c 个单位的作物；

  3. 农场 a 与农场 b 种植的作物数一样多。

由此，我们可以列出相应不等式：

\left\{ \begin{aligned} x_a-x_b &\geq c \\ x_a-x_b &\leq c \\ x_a=x_b \end{aligned} \right.

可以转换为

\left\{ \begin{aligned} x_b-x_a &\leq -c \\ x_a-x_b &\leq c \\ x_a-x_b &\leq 0,x_b-x_a \leq 0 \end{aligned} \right.

这么建图：

int opt,a,b,c;
scanf("%d",&opt);
if(opt==1)
{
    scanf("%d%d%d",&a,&b,&c);
    add(a,b,-c);
}
else if(opt==2)
{
    scanf("%d%d%d",&a,&b,&c);
    add(b,a,c);
}
else 
{
    scanf("%d%d",&a,&b);
    add(b,a,0);
    add(a,b,0);
}

然后就是模板了。

代码如下：


#include<iostream>
#include<cstdio>
#include<queue>
#include<string.h>//头文件，我不喜欢万能头
using namespace std;
int n,m;
int tot,fir[10005];
struct edge
{
    int nxt,to,val;
}e[15005];
void add(int u,int v,int w)
{
    e[++tot]={fir[u],v,w};fir[u]=tot;
}//链式前向星式建图qwq
int dis[15005],cnt[15005];
bool vis[15005];
queue<int>q;
bool SPFA(int s)
{
    memset(dis,0x3f,sizeof dis);//赋值MAX
    vis[s]=1;
    dis[s]=0;
    q.push(s);//先标记表示入队
    while(!q.empty())
    {
        int u=q.front();q.pop();//出队
        vis[u]=0;
        for(int i=fir[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].val)
            {
                dis[v]=dis[u]+e[i].val;
                cnt[v]++;
                if(cnt[v]==n)
                    return 0;//此时说明有负环
                if(vis[v]==0)
                {
                    vis[v]=1;
                    q.push(v);
                }//入队
            }
        }
    }
    return 1;
}//SPFA模板
int main()
{
    scanf("%d%d",&n,&m);
    int s=n+1;
    同上
    for(int i=1;i<=n;i++)
        add(s,i,0);
    if(SPFA(s)) cout<<"Yes";
    else cout<<"No";
    return 0;
}

于是，这道题就水过了。