洛谷3275 [SCOI2011]糖果

access_time    bookmark 题解    comment 0 条评论    提高+/省选-

题意

给 $N$ 个人分糖。有 $K$ 个要求,格式为 $(X,A,B)$ ,表示对第 $A$ 个人和第 $B$ 个人有第 $X$ 种限制,用 $S_i$ 表示第 $i$ 个人分得的糖数:

  • $X=1$ , $S_A=S_B$
  • $X=2$ , $S_A<S_B$
  • $X=3$ , $S_A\geq S_B$
  • $X=4$ , $S_A>S_B$
  • $X=5$ , $S_A\le S_B$

求最少需要准备的糖数,如果无法满足所有要求输出 $-1$ 。

其中 $N\le 100000$ 。

题解

显然差分约束,对上述条件建边如下:

  • $X=1$ , $add(A,B,0),add(B,A,0)$
  • $X=2$ , $add(A,B,1)$
  • $X=3$ , $add(B,A,0)$
  • $X=4$ , $add(B,A,1)$
  • $X=5$ , $add(A,B,0)$

因为每个人至少一颗糖,所以 $\sum ^{n}_{i=1} add(0,i,1)$

对于无解有两种情况:

  1. $X=2$ 或 $X=4$ 中出现 $A=B$
  2. 存在负环

所以从节点 $0$ 开始跑 $spfa$ ,顺便判断负环即可。

玄学的是对于第 $6$ 个点,对 $0$ 到各个点正序加边可以过,但逆序会T(前向星是反的)。于是我从loj上下了数据,并对 $X$ 进行了分析:

数据(因为从0开始编号实为第5个)

#include<bits/stdc++.h>

using namespace std;

int cnt[5],n,m,x,y,z;

int main()
{
    freopen("candy5.in","r",stdin);
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        cnt[x]++;
    }
    cout<<cnt[2]<<" "<<cnt[4]<<endl;
    return 0;
}

结果:

50059 49940

看来 $X=2$ 比 $X=4$ 要多,也就是说正序边比逆序多,所以对于广搜来说正序开始搜应该会更快得到最优解。虽然我总觉得这个理论站不住脚但也只能这么认为了

下面上这道题的代码:

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to,w;
} edge[300005];
int cnt,head[100005],n,m,a,b,x,dis[100005],c[100005];
bool in[100005];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline ll spfa()
{
    memset(dis,-0x3f,sizeof(dis));
    dis[0]=0;
    queue <int> q;
    q.push(0);
    while (!q.empty())
    {
        int x=q.front(); q.pop();
        in[x]=0;
        c[x]++;
        if (c[x]==n) return -1;
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,w=edge[i].w;
            if (dis[x]+w>dis[y])
            {
                dis[y]=dis[x]+w;
                if (in[y]) continue;
                in[y]=1;
                q.push(y);
            }
        }
    }
    ll ans=0;
    for (int i=1;i<=n;i++) ans+=dis[i];
    return ans;
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        x=read(); a=read(); b=read();
        if (x==1) add(a,b,0),add(b,a,0);
        else if (x==2) { if (a-b) add(a,b,1); else return !printf("-1"); }
        else if (x==3) add(b,a,0);
        else if (x==4) { if (a-b) add(b,a,1); else return !printf("-1"); }
        else add(a,b,0);
    }
    for (int i=n;i;i--) add(0,i,1);
    printf("%lld",spfa());
    return 0;
}

新评论

account_circle
称呼不能为空
email
邮箱格式不合法
link
网站格式不合法
textsms
内容不能为空

第一次提交的评论将在审核后显示。