poj1275 差分约束 (二)

2014-11-24 03:23:26 · 作者: · 浏览: 2
while(n--)
{
int time;
scanf("%d",&time);
t[time+1]++;
}
for(i=1;i<=24;i++)
s[i]=s[i-1]+t[i];

///////////////////////////
//此部分建固有边
m=0;
n=24;
for(i=1;i<=24;i++)
{
e[m].u=i-1;
e[m].v=i;
e[m].w=0;
m++;
e[m].u=i;
e[m].v=i-1;
e[m].w=-t[i];
m++;
}
for(i=1;i<=16;i++)
{
j=i+8;
e[m].u=i;
e[m].v=j;
e[m].w=r[j];
m++;

}
//////////////////////////////
int mm=m;
for(sum=0;sum<=s[24];sum++)
{
m=mm;
for(i=17;i<=24;i++)
{
j=i-16;
e[m].u=i;
e[m].v=j;
e[m].w=r[j]-sum;
m++;
}
e[m].u=0;
e[m].v=24;
e[m].w=sum;
m++;
if(Bellman_Ford())
break;
}
if(sum<=s[24])
printf("%d\n",sum);
else
printf("No Solution\n");
}
return 0;
}