题解 P4578 【[FJOI2018]所罗门王的宝藏】

未见堇开 · 2019-03-20 22:03:29 · 题解

差分约束做法。

设第r行的操作使这一行的数增加了x_{r}，第c列的操作使这一列的数减少了y_{c}，

那么显然对于第r行第c列绿宝石的密码p，有x_{r}-y_{c}=p

即：\left\{\begin{matrix}x_{r}-y_{c}\leq p\\x_{r}-y_{c}\geq p\end{matrix}\right.

移项得\left\{\begin{matrix}x_{r}-y_{c}\leq p\\y_{c}-x_{r}\leq -p\end{matrix}\right.

对两个不等式分别连边(r\overset {p}{\rightarrow}c+n)\; ,\; (c+n\overset {-p}{\rightarrow}r)，即可构造差分约束系统。

因为题目只求解的存在性，判负环即可。

讲解到此为止。放代码。

#include<cstdio>
#include<queue>
#define reg register
#define MAXN 2019
using namespace std;

struct edge
{int pre,dis,to;}e[5005];
int n,m,k,s,ptr_e;
bool have=false;
int last[MAXN],dis[MAXN],inq[MAXN],vis[MAXN];

inline void spfa()
{
    dis[s]=0;
    queue<int> q; 
    for(int i=1;i<=n+m;i++)
        dis[i]=0x23333333,inq[i]=vis[i]=0;
    q.push(s),vis[s]=1;
    while(!q.empty())
    {
        int tmp=q.front();
        q.pop(),inq[tmp]=0;
        for(reg int i=last[tmp];i;i=e[i].pre)
        {
            int v=e[i].to,w=e[i].dis;
            if(dis[v]>dis[tmp]+w)
            {
                if(vis[v]>=n+m)
                {
                    have=true;
                    return;
                }
                dis[v]=dis[tmp]+w;
                if(!inq[v])
                {
                    ++vis[v],inq[v]=1;
                    q.push(v);
                }
            }
        }
    }
    have=false;
    return;
}

inline void addedge(int u,int v,int d)//连边
{
    e[++ptr_e].pre=last[u];
    e[ptr_e].dis=d,e[ptr_e].to=v,last[u]=ptr_e;
    return;
}

inline int qin()//快读
{
    reg int ans=0,m=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            m=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        ans=ans*10+(ch-'0');
        ch=getchar();
    }
    return(ans*m);
}

int main()
{
    int t=qin();
    while(t--)
    {
        n=qin(),m=qin(),k=qin();
        ptr_e=0,s=n+m+1;
        last[s]=0;
        for(reg int i=1;i<=n+m;i++)
            last[i]=0,addedge(s,i,0);
        while(k--)
        {
            int u=qin(),v=qin(),d=qin();
            addedge(u,v+n,d),addedge(n+v,u,-d);
        }
        spfa();
        if(have)
            puts("No");
        else
            puts("Yes");
    }
    return(0);
}

97msAC