2014
03-09

# Inviting Friends

You want to hold a birthday party, inviting as many friends as possible, but you have to prepare enough food for them. For each person, you need n kinds of ingredient to make good food. You can use the ingredients in your kitchen, or buy some new ingredient packages. There are exactly two kinds of packages for each kind of ingredient: small and large.

We use 6 integers to describe each ingredient: x, y, s1, p1, s2, p2, where x is the amount (of this ingredient) needed for one person, y is the amount currently available in the kitchen, s1 and p1 are the size (the amount of this ingredient in each package) and price of small packages, s2 and p2 are the size and price of large packages.

Given the amount of money you can spend, your task is to find the largest number of person who can serve. Note that you cannot buy only part of a package.

There are at most 10 test cases. Each case begins with two integers n and m (1<=n<=100, 1<=m<=100000), the number of kinds of ingredient, and the amount of money you have. Each of the following n lines contains 6 positive integers x, y, s1, p1, s2, p2 to describe one kind of ingredient (10<=x<=100, 1<=y<=100, 1<=s1<=100, 10<=p1<=100, s1<s2<=100, p1<p2<=100). The input ends with n = m = 0.

There are at most 10 test cases. Each case begins with two integers n and m (1<=n<=100, 1<=m<=100000), the number of kinds of ingredient, and the amount of money you have. Each of the following n lines contains 6 positive integers x, y, s1, p1, s2, p2 to describe one kind of ingredient (10<=x<=100, 1<=y<=100, 1<=s1<=100, 10<=p1<=100, s1<s2<=100, p1<p2<=100). The input ends with n = m = 0.

2 100
10 8 10 10 13 11
12 20 6 10 17 24
3 65
10 5 7 10 13 14
10 5 8 11 14 15
10 5 9 12 15 16
0 0

5
2

->题目请戳这里<-

+ s2-1，求出最小值返回即可。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 104;
const int INF = 0x3fffff;
const double eps = 1e-4;
struct node
{
int per,remain,s1,p1,s2,p2;
double ave1,ave2;
}lcm[N];
int n,m;

int dp[1110000];
int pack(int cur,int sum)
{
int i;
int a=min(lcm[cur].s1,lcm[cur].s2);
int b=max(lcm[cur].s1,lcm[cur].s2);
if(sum < a)
return min(lcm[cur].p1,lcm[cur].p2);    sum+=b-1;
for(i=1;i<=sum;i++)
dp[i]=INF;
dp[0]=0;
for(i=1;i<=sum;i++)
if(i>=lcm[cur].s1&&((i-lcm[cur].s1==0)||dp[i-lcm[cur].s1]))
dp[i]=min(dp[i],dp[i-lcm[cur].s1]+lcm[cur].p1);
for(i=1;i<=sum;i++)
if(i>=lcm[cur].s2&&((i-lcm[cur].s2==0)||dp[i-lcm[cur].s2]))
dp[i]=min(dp[i],dp[i-lcm[cur].s2]+lcm[cur].p2);
int ans=INF;
for(i=sum-(b-1);i<=sum;i++)
ans=min(ans,dp[i]);
return ans;
}

int isok(int x)
{
int money = m;
int i;
for(i = 0;i < n;i ++)
{
int need = lcm[i].per * x - lcm[i].remain;
money -= pack(i,need);
if(money < 0)
return 0;
}
if(money < 0)
return 0;
return 1;
}

int main()
{
int cnt,i;
while(scanf("%d%d",&n,&m),(m + n))
{
int mx = 100000;
for(i = 0;i < n;i ++)
{
scanf("%d%d%d%d%d%d",&lcm[i].per,&lcm[i].remain,&lcm[i].s1,&lcm[i].p1,&lcm[i].s2,&lcm[i].p2);
lcm[i].ave1 = (double)lcm[i].s1 / (lcm[i].p1 * 1.0);
lcm[i].ave2 = (double)lcm[i].s2 / (lcm[i].p2 * 1.0);
int tmp = m / lcm[i].p2;
cnt = (m - lcm[i].p2 * tmp) * lcm[i].s1 / lcm[i].p1 + tmp * lcm[i].s2;
cnt += lcm[i].remain;
cnt /= lcm[i].per;
if(mx > cnt)
mx = cnt;
}
int l = 1;
int r = mx;
int mid;
int ans;
while(l <= r)
{
mid = (l + r)>>1;
if(!isok(mid))
r = mid - 1;
else
{
ans = mid;
l = mid + 1;
}
}
printf("%d\n",ans);
}
return 0;
}

2. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;