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

Xorex's blog

纵然希望渺茫,也要做一条有梦想的咸鱼!

 
 
 
 
 

日志

 
 
关于我

本人倒是一直被吊着打啊……

文章分类

差分约束系统  

2017-05-11 12:26:05|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
差分约束系统其实就是一种限制的关系,转换为一张图,然后跑一边SPFA,更新一遍,具体就看两道题吧。

P1984奖学金
期末考试终于完了,老班决定召开班委会,内容嘛,则是可爱的奖学金的问题,她叫来了一些班委,每位班委提出了自己的意见:“我认为同学a的奖学金应该比b多!”老班决定要找出一种奖学金方案,满足各位班委的意见,且同时使得总奖学金数最少。每位同学奖学金最少为100元且都为整数。
输入:
第一行两个整数n,m,表示同学总数和班委意见数; 以下m行,每行2个整数a,b,表示某个班委认为第a号同学奖学金应该比第b号同学高
输出:
若无法找到合法方案,则输出“impossible”(不含引号);否则输出一个数表示最少总奖学金。

我们将里面的a>b转换为a=b+1,就可以建造一张这样的关系图了b到a存在着边权为1的路,然后我们就跑一遍SPFA美滋滋,更新出来所有符合要求的奖学金,如果不符合要求就直接退出输出impossible,如果符合就累加起来输出。
code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct Edge
{
int Point;
int Next;
}a[20000];
int n,m,x,y,Link[20000],len;
int dis[20000],Queue[20000];
long long head,tail,ans,Money[20000];
inline int In()
{
int This=0,F=1; char ch=getchar();
while(ch<'0'||ch>'9')
{ if(ch=='-') F=-F; ch=getchar();}
while(ch>='0'&&ch<='9')
{ This=(This<<1)+(This<<3)+ch-'0';ch=getchar();}
return This*F;
}
bool Topsort_SPFA()
{
for(int i=1;i<=n;i++)
if(!dis[i]) Queue[++tail]=i;
while(++head<=tail)
for(int i=Link[Queue[head]];i;i=a[i].Next)
{
int This=a[i].Point; dis[This]--;
Money[This]=max(Money[This],Money[Queue[head]]+1);
if(!dis[This]) Queue[++tail]=This;
if(dis[This]<0) return false;
}
sort(Money+1,Money+n+1);
if(Money[1]<0) return false;
else return true;
}
int main()
{
n=In(); m=In();
for(int i=1;i<=m;i++)
{
y=In(); x=In();
a[++len].Point=y;
a[len].Next=Link[x];
Link[x]=len;
dis[y]++;
}
for(int i=1;i<=n;i++) Money[i]=100;
if(!Topsort_SPFA()||tail!=n) cout<<"impossible"<<endl;
else {
for(int i=1;i<=n;i++) ans+=Money[i];
cout<<ans<<endl;
}
return 0;
}



P1985糖果
幼儿园里有N个小朋友,lxhgww老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候,lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的,lxhgww想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。
输入:
第一行是两个整数N,K。 接下来K行,表示这些点需要满足的关系,每行3个数字,X,A,B。 如果X=1, 表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多; 如果X=2, 表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果; 如果X=3, 表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果; 如果X=4, 表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果; 如果X=5, 表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果;
输出:
输出一行,表示lxhgww老师至少需要准备的糖果数,如果不能满足小朋友们的所有要求,就输出-1。
这道题好烦好烦,因为这道题不但麻烦的,而且第六组数据时需要进行逆向加边的,因为顺着地会超时,没错,十万个点的一条链,然后是就是理所应当的超时了,所以我们需要逆向加边……心累不说了,我要去搞树状数组了!QAQ
code:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
struct Edge
{
int Point;
int Next;
int Value;
}a[2000000];
int n,m,x,y,z,len,head,tail,Queue[200000];
int Link[200000],Candy[200000],dis[200000];
long long ans;
bool vis[200000];
inline int In()
{
int This=0,F=1; char ch=getchar();
while(ch<'0'||ch>'9')
{ if(ch=='-') F=-F; ch=getchar();}
while(ch>='0'&&ch<='9')
{ This=(This<<1)+(This<<3)+ch-'0';ch=getchar();}
return This*F;
}
void Init(int x,int y,int v)
{
a[++len].Point=y;
a[len].Next=Link[x];
a[len].Value=v;
Link[x]=len;
}
bool SPFA()
{
Queue[++tail]=0;
vis[0]=true;
dis[0]=true;
while(++head<=tail)
{
cout<<Queue[head]<<endl;
for(int i=Link[Queue[head]];i;i=a[i].Next)
{
int This=a[i].Point;
if(Candy[This]<Candy[Queue[head]]+a[i].Value)
{
Candy[This]=Candy[Queue[head]]+a[i].Value;
if(++dis[This]>=n) return false;
if(vis[This]==false)
{
Queue[++tail]=This;
vis[This]=true;
}
}
}
vis[Queue[head]]=false;
}
}
int main()
{
n=In(); m=In();
for(int i=1;i<=m;i++)
{
z=In(); x=In(); y=In();
if(z==1)
{
Init(x,y,0);
Init(y,x,0);
}
if(z==2)
{
if(x==y)
{
cout<<-1<<endl;
return 0;
}
Init(x,y,1);
}
if(z==3) Init(y,x,0);
if(z==4)
{
if(x==y)
{
cout<<-1<<endl;
return 0;
}
Init(y,x,1);
}
if(z==5) Init(x,y,0);
}
for(int i=n;i;i--) Init(0,i,1);
if(!SPFA()) cout<<-1<<endl;
else {
for(int i=1;i<=n;i++)
ans+=Candy[i];
cout<<ans<<endl;
}
return 0;
}






  评论这张
 
阅读(36)| 评论(0)

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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