洛谷3275 [SCOI2011]糖果

题意

给 $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)$

对于无解有两种情况：

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

所以从节点 $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;
}

题意

题解

新评论