差分约束系统
说白了就是求不等式组 若不了解差分约束系统推荐看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 阅读(1018) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年3月>
22232425262728
1234567
891011121314
15161718192021
22232425262728
2930311234

留言簿(6)

随笔分类

随笔档案

文章档案

相册

搜索

  •  

最新评论