差分約束系統(tǒng)
說白了就是求不等式組 若不了解差分約束系統(tǒng)推薦看WC06 馮威論文
對于這個題 設xi為第i時刻實際雇傭人數(shù) 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個不等式中出現(xiàn)了3個未知數(shù) 但s24重復出現(xiàn)所以可以枚舉s24 還可以二分優(yōu)化
下面是我的代碼
#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 閱讀(1033)
評論(0) 編輯 收藏 引用