首页 > 搜索 > BFS搜索 > HDU 2883-kebab-BFS-[解题报告]HOJ
2014
02-17

HDU 2883-kebab-BFS-[解题报告]HOJ

kebab

问题描述 :

Almost everyone likes kebabs nowadays (Here a kebab means pieces of meat grilled on a long thin stick). Have you, however, considered about the hardship of a kebab roaster while enjoying the delicious food? Well, here’s a chance for you to help the poor roaster make sure whether he can deal with the following orders without dissatisfying the customers.

Now N customers is coming. Customer i will arrive at time si (which means the roaster cannot serve customer i until time si). He/She will order ni kebabs, each one of which requires a total amount of ti unit time to get it well-roasted, and want to get them before time ei(Just at exactly time ei is also OK). The roaster has a big grill which can hold an unlimited amount of kebabs (Unbelievable huh? Trust me, it’s real!). But he has so little charcoal that at most M kebabs can be roasted at the same time. He is skillful enough to take no time changing the kebabs being roasted. Can you help him determine if he can meet all the customers’ demand?

Oh, I forgot to say that the roaster needs not to roast a single kebab in a successive period of time. That means he can divide the whole ti unit time into k (1<=k<=ti) parts such that any two adjacent parts don’t have to be successive in time. He can also divide a single kebab into k (1<=k<=ti) parts and roast them simultaneously. The time needed to roast one part of the kebab well is linear to the amount of meat it contains. So if a kebab needs 10 unit time to roast well, he can divide it into 10 parts and roast them simultaneously just one unit time. Remember, however, a single unit time is indivisible and the kebab can only be divided into such parts that each needs an integral unit time to roast well.

输入:

There are multiple test cases. The first line of each case contains two positive integers N and M. N is the number of customers and M is the maximum kebabs the grill can roast at the same time. Then follow N lines each describing one customer, containing four integers: si (arrival time), ni (demand for kebabs), ei (deadline) and ti (time needed for roasting one kebab well).

There is a blank line after each input block.

Restriction:
1 <= N <= 200, 1 <= M <= 1,000
1 <= ni, ti <= 50
1 <= si < ei <= 1,000,000

输出:

There are multiple test cases. The first line of each case contains two positive integers N and M. N is the number of customers and M is the maximum kebabs the grill can roast at the same time. Then follow N lines each describing one customer, containing four integers: si (arrival time), ni (demand for kebabs), ei (deadline) and ti (time needed for roasting one kebab well).

There is a blank line after each input block.

Restriction:
1 <= N <= 200, 1 <= M <= 1,000
1 <= ni, ti <= 50
1 <= si < ei <= 1,000,000

样例输入:

2 10
1 10 6 3
2 10 4 2

2 10
1 10 5 3
2 10 4 2

样例输出:

Yes
No

题意:有n个顾客,每个顾客Si时间到达,会点ni个肉串,每个肉串用ti单位时间能烤好,这个顾客想要在Ei时间前得到肉串(包括Ei)。卖主每单位时间能烤M单位的肉串,问最后能否令所有的顾客满足。

思路:最大流判满流。先建立一个源点S和汇点T,从S向每个顾客连一条容量为ni*ti的边,再从每个顾客向每个时间段连一条容量为inf的边,最后从每个时间段向T连一条M*时间段长度的边,这样以后求一下最大流,如果等于Σni*ti,那么说明能满足所有顾客,否则不能。这里要注意的是,由于时间的范围很大, 所以不能直接向每一天添加边,把所有的时间排个序,然后计算一个时间段,每次向时间段添加边即可,还有题目说每个肉串可以分成k份在不同时间烤,这样的话只要把ni*ti看成一个量就行了。

 

代码:

#include <iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#define inf 2139062143
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
const int maxn=1000+10;
const int N=1000000+10;
struct Edge
{
    int from,to,cap,flow;
};
struct Query
{
    int S,ni,E,ti;
};
struct Dinic
{
    vector<Edge>edges;
    vector<int>G[maxn];
    bool vis[maxn];
    int d[maxn],cur[maxn];
    int n,m,s,t;
    void Init(int n)
    {
        for(int i=0;i<=n;++i) G[i].clear();
        edges.clear();
    }
    void AddEdges(int from,int to,int cap)
    {
        edges.push_back((Edge){from,to,cap,0});
        edges.push_back((Edge){to,from,0,0});
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    bool BFS()
    {
        queue<int>q;
        memset(vis,0,sizeof(vis));
        vis[s]=true;
        d[s]=0;
        q.push(s);
        while(!q.empty())
        {
            int x=q.front();q.pop();
            for(int i=0;i<G[x].size();++i)
            {
                Edge e=edges[G[x][i]];
                if(!vis[e.to]&&e.cap>e.flow)
                {
                    d[e.to]=d[x]+1;
                    vis[e.to]=true;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a)
    {
        if(x==t||a==0) return a;
        int flow=0,f;
        for(int & i=cur[x];i<G[x].size();++i)
        {
            Edge & e=edges[G[x][i]];
            if(d[e.to]==d[x]+1&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)
            {
                flow+=f;
                edges[G[x][i]].flow+=f;
                edges[G[x][i]^1].flow-=f;
                a-=f;
                if(a==0) break;
            }
        }
        return flow;
    }
    int Maxflow(int s,int t)
    {
        this->s=s;this->t=t;
        int flow=0;
        while(BFS())
        {
            memset(cur,0,sizeof(cur));
            flow+=DFS(s,inf);
        }
        return flow;
    }
}dinic;
Query query[300];
int convert[N],dd[500],val[maxn];
int getCon(int sz)
{
    sort(dd+1,dd+sz);
    int u=1;
    int i=1,j=1;
    for(i=2;i<sz;++i)
    {
        if(dd[i]==dd[j]) continue;
        dd[++j]=dd[i];
    }
    for(i=1;i<j;++i)
    {
        convert[dd[i]]=u;
        val[u]=dd[i+1]-dd[i];
        u++;
    }
    convert[dd[i]]=u;
    val[u]=0;
    return u;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        int sum=0;
        int sz=1;
        for(int i=1;i<=n;++i)
        {
            scanf("%d%d%d%d",&query[i].S,&query[i].ni,&query[i].E,&query[i].ti);
            sum+=query[i].ni*query[i].ti;
            dd[sz++]=query[i].S;
            dd[sz++]=query[i].E;
        }
        sz=getCon(sz);
        int N=n+sz+1;
        dinic.Init(N);
        for(int i=1;i<=n;++i)
        {
            dinic.AddEdges(0,i,query[i].ni*query[i].ti);
            int t=convert[query[i].S];
            while(t!=convert[query[i].E])
            {
                dinic.AddEdges(i,n+t,inf);
                t++;
            }
        }
        for(int i=1;i<sz;++i)
            dinic.AddEdges(n+i,N,m*val[i]);
        int res=dinic.Maxflow(0,N);
        if(res==sum)
           printf("Yes\n");
        else
           printf("No\n");
    }
    return 0;
}

 

解题参考:http://blog.csdn.net/qian99/article/details/9771441


, ,