差分约束系统
说白了就是求不等式组 若不了解差分约束系统推荐看WC06 冯威论文
对于这个题 设xi为第i时刻实际雇佣人数 numi为上限 si=si-1+xi，s0=0 ri题目中提到 则
numi>=si-si-1>=0
si-si-8>=ri （i>=8）
si+s24-si+16>=ri (i<8)
在第3个不等式中出现了3个未知数 但s24重复出现所以可以枚举s24 还可以二分优化
下面是我的代码
#include<iostream>
using namespace std;
int n,m,dis[1000],num[25],r[25];
struct
{
int u,v,d;
}e[1000];
inline bool relax(int u,int v,int w)
{
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
return true;
}
return false;
}
inline bool getdis()
{
for(int i=1;i<=n;i++) dis[i]=1<<30;
dis[0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
relax(e[j].u,e[j].v,e[j].d);
for(int i=1;i<=m;i++)
if(relax(e[i].u,e[i].v,e[i].d))
return false;
return true;
}
inline void adde(int a,int b,int c)
{
e[++m].u=a;
e[m].v=b;
e[m].d=-c;
}
int main()
{
freopen("input.in","r",stdin);
freopen("output.out","w",stdout);
n=24;
for(int i=1;i<=n;++i)
scanf("%d",r+i);
int g;
scanf("%d",&g);
for(int i=1;i<=g;++i)
{
int p;
scanf("%d",&p);
++num[p+1];
}
int s=g,ed=-1;
for(;;)
{
if(s==ed+1)
{
printf("%d\n",s);
return 0;
}
m=0;
int t=(s+ed)/2;
for(int i=1;i<=n;++i)
{
adde(i,i-1,0);
adde(i-1,i,-num[i]);
}
for(int i=8;i<=n;++i)
adde(i,i-8,r[i]);
for(int i=1;i<8;++i)
adde(i,i+16,r[i]-t);
if(getdis())
s=t;
else
ed=t;
}
}
posted on 2009-03-20 01:10
250 阅读(1025)
评论(0) 编辑 收藏 引用