BZOJ2662-[SCOI2011]糖果(spfa最长路+差分约束)

题目链接:BZOJ2662-SCOI2011-糖果

题意:

n个小朋友分糖果,要求某些小朋友之间的糖果数需要满足一定的数量关系,问最少需要多少颗糖果。

题解:

差分约束系统。

对于一对u,v,数量小的向数量大的连边,若严格小于权值设为1,非严格小于权值设为0;

然后由0点出发,向其他所有点连单向权值为1的边。(这里只能从n到1倒序加边才能AC,顺序加边会T,有一组数据超级坑,据hzwer称,这组数据是1e5个点连成一条链)

然后跑spfa最长路(dijkstra不能处理最长路QAQ),统计答案即可,需要long long。

PS.spfa真的是玄学算法

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+9;
const int MAXM=1e5+9;
const int inf=0x3f3f3f3f;
int n,m;
struct EDGE
{
    int v,w,nxt;
} edge[MAXM*4];
int cnt=0,fir[MAXN];
void addedge(int u,int v,int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].nxt=fir[u];
    fir[u]=cnt++;
}
int dis[MAXN],tot[MAXN];
bool used[MAXN];
bool spfa(int st)
{
    for(int i=1; i<=n; i++)
        dis[i]=-1;
    memset(tot,0,sizeof(tot));
    memset(used,0,sizeof(used));
    dis[st]=0;
    queue<int> que;
    while(!que.empty())
        que.pop();
    que.push(st);
    while(!que.empty())
    {
        int u=que.front();
        used[u]=0;
        que.pop();
        for(int i=fir[u]; i!=-1; i=edge[i].nxt)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(dis[v]<dis[u]+w)
            {
                dis[v]=dis[u]+w;
                tot[v]=tot[u]+1;
                if(tot[v]>n)
                    return 0;
                if(!used[v])
                {
                    que.push(v);
                    used[v]=1;
                }
            }
        }
    }
    return 1;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(fir,-1,sizeof(fir));
    for(int i=1; i<=m; i++)
    {
        int x,u,v;
        scanf("%d%d%d",&x,&u,&v);
        if(x==1)
        {
            addedge(u,v,0);
            addedge(v,u,0);
        }
        else    if(x==2)
        {
            if(u==v)
                return puts("-1"),0;
            addedge(u,v,1);
        }
        else    if(x==3)
            addedge(v,u,0);
        else    if(x==4)
        {
            if(u==v)
                return puts("-1"),0;
            addedge(v,u,1);
        }
        else    if(x==5)
            addedge(u,v,0);
    }
    for(int i=n; i>=1; i--)
        addedge(0,i,1);
    if(!spfa(0))
        return puts("-1"),0;
    ll ans=0;
    for(int i=1; i<=n; i++)
    {
        if(dis[i]==-1)
            return puts("-1"),0;
        ans+=1ll*dis[i];
    }
    printf("%lld\n",ans);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。