图论--网络流--最大流 HDU 2883 kebab（离散化）

Problem Description

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.

Input

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

Output

If the roaster can satisfy all the customers, output “Yes” (without quotes). Otherwise, output “No”.

Sample Input

Sample Output

Yes 
No

这个题就是基本的最大流，怎么建图，源点到每个人建边，流量设置为点羊肉串数量。然后每个人到他那个时间段的每一个边都设流量为INF，然后，时间点到汇点的边设置为M即，烤炉最多一次考多少串串。但是这里要考虑到点的范围1000000，这样建图真的会超时，我看了RQ的博客，看到了这里是可以离散化建图，就是说，将每个点看成一段时间的集合，如过时间有交叉就要把那段时间单独处理，这样它覆盖了多少点，就有多少个M然后最大流。

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#define INF 1e9
using namespace std;
const int maxn=600+5;
 
struct Edge
{
    int from,to,cap,flow;
    Edge(){}
    Edge(int f,int t,int c,int fl):from(f),to(t),cap(c),flow(fl){}
};
 
struct Dinic
{
    int n,m,s,t;
    vector<Edge> edges;
    vector<int> G[maxn];
    int d[maxn];
    int cur[maxn];
    bool vis[maxn];
 
    void init(int n,int s,int t)
    {
        this->n=n, this->s=s, this->t=t;
        edges.clear();
        for(int i=0;i<n;++i) G[i].clear();
    }
 
    void AddEdge(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)
                {
                    vis[e.to]=true;
                    d[e.to]=d[x]+1;
                    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)
            {
                e.flow +=f;
                edges[G[x][i]^1].flow -=f;
                flow +=f;
                a -=f;
                if(a==0) break;
            }
        }
        return flow;
    }
 
    int max_flow()
    {
        int ans=0;
        while(BFS())
        {
            memset(cur,0,sizeof(cur));
            ans += DFS(s,INF);
        }
        return ans;
    }
}DC;
 
int N,M;
int s[maxn],n[maxn],e[maxn],t[maxn];
int time[maxn];
int full_flow;
 
int main()
{
    while(scanf("%d%d",&N,&M)==2)
    {
        full_flow=0;
        int cnt=0;
        for(int i=1;i<=N;i++)
        {
            scanf("%d%d%d%d",&s[i],&n[i],&e[i],&t[i]);
            time[cnt++]=s[i];
            time[cnt++]=e[i];
            full_flow += n[i]*t[i];
        }
        sort(time,time+cnt);
        cnt = unique(time,time+cnt)-time;//去重
        int src=0,dst=N+cnt+1;
        DC.init(N+cnt+2,src,dst);
 
        for(int i=1;i<=N;i++) DC.AddEdge(src,i,n[i]*t[i]);
        for(int i=1;i<=cnt-1;++i)
        {
            DC.AddEdge(N+i,dst,(time[i]-time[i-1])*M);
            for(int j=1;j<=N;++j)
                if(s[j]<=time[i-1] && time[i]<=e[j])
                    DC.AddEdge(j,N+i,INF);
        }
        printf("%s
",DC.max_flow()==full_flow?"Yes":"No");
    }
    return 0;
}