注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2330][SCOI2011]糖果  

2014-12-01 20:09:10|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2330: [SCOI2011]糖果

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 2445  Solved: 690
[Submit][Status]

Description

幼儿园里有N个小朋友,lxhgww老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候,lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的,lxhgww想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。

Input

输入的第一行是两个整数NK

接下来K行,表示这些点需要满足的关系,每行3个数字,XAB

如果X=1, 表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多;

如果X=2, 表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果

如果X=3, 表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果

如果X=4, 表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果

如果X=5, 表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果;

Output

输出一行,表示lxhgww老师至少需要准备的糖果数,如果不能满足小朋友们的所有要求,就输出-1

Sample Input

5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1

Sample Output

11

HINT

【数据范围】

对于30%的数据,保证 N<=100

对于100%的数据,保证 N<=100000

对于所有的数据,保证 K<=100000,1<=X<=5,1<=A, B<=N

Solution

若A<=B,则add(A,B,0)

若A<B,则add(A,B,1)

0往每个点连权值为1的边

跑最长路,如果某个点入队次数超过一定限制,则有很大概率存在正权环,则为无解

Code

/**************************************************************
    Problem: 2330
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:200 ms
    Memory:23440 kb
****************************************************************/
 
#include<cstdio>
int aa;char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 100010
int n,m,d[N],in[N],et,la[N],x,y,i,k,l,r,q[4<<20],cnt[N];long long ans;
struct E{int to,v,nxt;}e[N*4];
#define add(x,y,v) (e[++et]=(E){y,v,la[x]},la[x]=et)
#define cmin(a,b) (a>b?a=b:1)
#define cmax(a,b) (a<b?a=b:1)
int main()
{
    for(n=F(),m=F();m--;)
    {
        k=F(),x=F(),y=F();
        if(k==1)add(x,y,0),add(y,x,0);
        else if(k==2)if(x==y)return puts("-1"),0;else add(x,y,1);
        else if(k==3)add(y,x,0);
        else if(k==4)if(x==y)return puts("-1"),0;else add(y,x,1);
        else add(x,y,0);
    }
    for(i=n;i;i--)add(0,i,1);
    for(in[0]=1;l<=r;in[q[l++]]=0)
    for(i=la[q[l]];i;i=e[i].nxt)
    if(d[e[i].to]<d[q[l]]+e[i].v)
    {
        d[e[i].to]=d[q[l]]+e[i].v;
        if(!in[e[i].to])in[q[++r]=e[i].to]=1,cnt[e[i].to]++;
        if(cnt[e[i].to]>15)return puts("-1"),0;
    }
    for(i=1;i<=n;i++)ans+=d[i];
    printf("%lld\n",ans);
}
  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018