8
22
2015
0

[BZOJ2330] [SCOI2011] 糖果

我最喜欢的题目就是简单题了。(没办法我是蒟蒻)

差分约束现学现卖

这题搞个差分约束,注意数据有个超长的链,倒着加边就行。

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
//不要问为什么每个数组都是1000005……因为方便~
int n,k,en,h[1000005],cir[1000005],d[1000005],flg[1000005];
long long ans=0;

struct Edge{
int b,v,next;
}e[1000005];

void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

int spfa(){
//memset(d,0x3f,sizeof(d));
queue<int> Q;
Q.push(0);
d[0]=0;
flg[0]=1;
cir[0]=1;
int u,v;
while(!Q.empty()){
    u=Q.front();
    Q.pop();
    flg[u]=0;
    for(int i=h[u];i;i=e[i].next){
        v=e[i].b;
        if(d[u]+e[i].v>d[v]){
            d[v]=d[u]+e[i].v;
            if(++cir[v]>=n)return 1;
            if(!flg[v]){
                Q.push(v);
                flg[v]=1;
            }
        }
    }
}
return 0;
}

int main(){
freopen("2330.in","r",stdin);
freopen("2330.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=0;i<k;i++){
int x,a,b;
scanf("%d %d %d",&x,&a,&b);
if(x==1){add(a,b,0);add(b,a,0);continue;}
if(x==2){if(a==b){printf("-1\n");return 0;}add(a,b,1);continue;}
if(x==3){add(b,a,0);continue;}
if(x==4){if(a==b){printf("-1\n");return 0;}add(b,a,1);continue;}
if(x==5){add(a,b,0);continue;}
}
for(int i=n;i>0;i--)add(0,i,1);
if(spfa()){printf("-1\n");return 0;}
//for(int i=1;i<=n;i++)printf("%d\n",d[i]);
for(int i=1;i<=n;i++)ans+=d[i];
printf("%lld\n",ans);
return 0;
}
Category: BZOJ | Tags: OI | Read Count: 614

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com