uva Monkeys in the Emei Mountain(区间模型)

                                                    Monkeys in the Emei  Mountain

题目：

  给出N之猴子，每只猴子要喝v升的水，每个小时只能喝一升的水，并且只能在[a,b]时间段进行喝水，时间可以不连续，但是每次喝水必须是一个正的单位且不小于1小时。而喝水的地方就一个，一次只能容纳m只猴子。现在要你判断是否能在满足全部的猴子喝水。

算法：

  网络流的区间模型。常规做回超时，这题跟hdu kebab的模型一样，那题利索的多。这题输出太烦人了。做了一下建图模型不想再写了。给出一个别人的博客，还有建图模型可以看我之前的区间模型分析 。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int inf=1<<29;
const int maxn=410;
const int maxm=maxn*maxn;
struct Node
{
    int v;
    int l;
    int r;
    Node(){}
    Node(int sl,int sr)
    {
        l=sl;
        r=sr;
    }
    bool operator < (const Node &a)const
    {
        if(l==a.l)
            return r<a.r;
        return l<a.l;
    }
}monk[110];
int e,st,des,n,m,head[maxn],pnt[maxm],nxt[maxm],flow[maxm],level[maxn];
int t[300],hasuse[maxn][6],cnt;
queue<int> q;
vector<Node> arr;
void AddEdge(int u,int v,int f)
{
    pnt[e]=v;nxt[e]=head[u];flow[e]=f;head[u]=e++;
    pnt[e]=u;nxt[e]=head[v];flow[e]=0;head[v]=e++;
}
bool BFS(int st,int des)
{
    memset(level,0,sizeof(level));
    level[st]=1;
    q.push(st);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=nxt[i])
            if(flow[i]&&!level[pnt[i]])
            {
                level[pnt[i]]=level[u]+1;
                q.push(pnt[i]);
            }
    }
    return level[des];
}
int DFS(int u,int maxf)
{
    if(u==des||!maxf)
        return maxf;
    for(int i=head[u],t;i!=-1;i=nxt[i])
        if(level[pnt[i]]==level[u]+1&&(t=DFS(pnt[i],min(maxf,flow[i]))))
        {
            flow[i]-=t;
            flow[i^1]+=t;
            return t;
        }
    return level[u]=0;
}
int maxflow()
{
    int ans=0;
    while(BFS(st,des))
        while(1)
        {
            int f=DFS(st,inf);
            if(!f)
                break;
            ans+=f;
        }
    return ans;
}
void solve(int tot)
{
    int ans=maxflow();
    if(ans<tot)
    {
        printf("No\n");
        return;
    }
    printf("Yes\n");
    memset(hasuse,0,sizeof(hasuse));
    for(int i=1;i<=n;i++)
    {
        arr.clear();
        for(int j=0;j<e;j+=2)
        {
            if(pnt[j^1]==i&&flow[j^1]&&pnt[j]<des)
            {
                int index=pnt[j]-n-1;
                int res=flow[j^1];
                for(int k=0;k<m;k++)
                {
                    if(hasuse[index][k]==t[index+1]-t[index])
                        continue;
                    if(hasuse[index][k]+res<=t[index+1]-t[index])
                    {
                        arr.push_back(Node(t[index]+hasuse[index][k],t[index]+hasuse[index][k]+res));
                        hasuse[index][k]+=res;
                        break;
                    }
                    else
                    {
                        res-=(t[index+1]-t[index]-hasuse[index][k]);
                        arr.push_back(Node(t[index]+hasuse[index][k],t[index+1]));
                        hasuse[index][k]=t[index+1]-t[index];
                        if(!res)
                            break;
                    }
                }
            }
        }
        sort(arr.begin(),arr.end());
        int index=0;
        for(int j=1;j<arr.size();j++)
        {
            if(arr[j].l==arr[j-1].r)
            {
                arr[j-1].r=arr[j].r;
                arr.erase(arr.begin()+j);
                j--;
            }
        }
        printf("%d",arr.size());
        if(arr.size()==0)
            printf(" (0,0)");
        for(int j=0;j<arr.size();j++)
            printf(" (%d,%d)",arr[j].l,arr[j].r);
        printf("\n");
    }
}
void Build()
{
    e=st=0;des=n+cnt+1;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)
        AddEdge(st,i,monk[i].v);
    for(int i=1;i<cnt;i++)
        AddEdge(n+i,des,m*(t[i]-t[i-1]));
    for(int i=1;i<=n;i++)
        for(int j=1;j<cnt;j++)
            if(monk[i].l<=t[j-1]&&monk[i].r>=t[j])
                AddEdge(i,j+n,t[j]-t[j-1]);
}
int main()
{
    int cas=1;
    while(scanf("%d",&n)&&n)
    {
        cnt=0;
        scanf("%d",&m);
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&monk[i].v,&monk[i].l,&monk[i].r);
            t[cnt++]=monk[i].l;
            t[cnt++]=monk[i].r;
            sum+=monk[i].v;
        }
        sort(t,t+cnt);
        cnt=unique(t,t+cnt)-t;
        printf("Case %d: ",cas++);
        Build();
        solve(sum);
    } 
    return 0;
}