hdoj 2883 kebab 【经典最大流】

刺骨的言语ヽ痛彻心扉 2022-08-11 09:28 155阅读 0赞

题目：[hdoj 2883 kebab ][hdoj 2883 kebab]

题意：现在有n个人要烤肉，有m个烤肉架，然后给出每个人的烤肉开始时间si，结束时间ei，以及要烤肉的串数num，还有拷一串的时间ti，然后问你能不能满足所有人的要求。

分析：这是一个比较经典的最大流，经典在于建图方法，这个题目难点在于时间跨度在0---100 0000，如果时间短的话就可以用题目3572的做法了。[点击打开链接][Link 1]

后面看了别人的建图方法，确实比较经典，经典在于把区间缩点了，这个题目的难点在于时间跨度大，那么我们可以把所有的时间点记录下来，然后排序，然后以这些时间点建图。

建图方案：

首先超级源点s到每个人 i 建容量为 num \* ti 边，

然后对于每个人的烤肉时间区间，枚举排序之后的所有的相邻时间点，相邻两点也组成一个区间，那么假如枚举的区间包含在这个人的时间区间内，从人 i 建边 区间 j，容量inf

然后每个区间开始点 j 建边到超级汇点建边容量为（time【j+1】-time【j】）\*m。

这样，如果最大流为所有的count（num \* ti），则满足要求。

样例1建图之后得到这样的图：

![Center][]

![Image 1][]

这个题目也是用c++提交的，G++编译错误，不解。

AC代码：

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <vector>
    #include <queue>
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    const int N = 1020;
    const int inf = 0x3f3f3f3f;
    int n,m;
    int Min(int a,int b)
    {
    	return a>b?b:a;
    }
    struct Node
    {
        int from,to,cap,flow;
    };
    vector<int> v[N];
    vector<Node> e;
    int vis[N];  //构建层次图
    int cur[N];
    void add_Node(int from,int to,int cap)
    {
    	Node tmp1,tmp2;
    	tmp1.cap=from=from,tmp1.to=to,tmp1.cap=cap,tmp1.flow=0;
        e.push_back(tmp1);
    	tmp2.from=to,tmp2.to=from,tmp2.cap=0,tmp2.flow=0;
        e.push_back(tmp2);
        int tmp=e.size();
        v[from].push_back(tmp-2);
        v[to].push_back(tmp-1);
    }
    bool bfs(int s,int t)
    {
        Del(vis,-1);
        queue<int> q;
        q.push(s);
        vis[s] = 0;
        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            for(int i=0;i<v[x].size();i++)
            {
                Node tmp = e[v[x][i]];
                if(vis[tmp.to]<0 && tmp.cap>tmp.flow)  //第二个条件保证
                {
                    vis[tmp.to]=vis[x]+1;
                    q.push(tmp.to);
                }
            }
        }
        if(vis[t]>0)
            return true;
        return false;
    }
    int dfs(int o,int f,int t)
    {
        if(o==t || f==0)  //优化
            return f;
        int a = 0,ans=0;
        for(int &i=cur[o];i<v[o].size();i++) //注意前面 ’&‘,很重要的优化
        {
            Node &tmp = e[v[o][i]];
            if(vis[tmp.to]==(vis[o]+1) && (a = dfs(tmp.to,Min(f,tmp.cap-tmp.flow),t))>0)
            {
                tmp.flow+=a;
                e[v[o][i]^1].flow-=a; //存图方式
                ans+=a;
                f-=a;
                if(f==0)  //注意优化
                    break;
            }
        }
        return ans;  //优化
    }
    
    int dinci(int s,int t)
    {
        int ans=0;
        while(bfs(s,t))
        {
            Del(cur,0);
            int tm=dfs(s,inf,t);
            ans+=tm;
        }
        return ans;
    }
    struct Node1
    {
        int si,num,ei,ti;
    };
    Node1 a[250];
    vector<int> time;
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            int s=0,t=3*n+2,count=0,i,j;
            for(i=1;i<=n;i++)
            {
                scanf("%d%d%d%d",&a[i].si,&a[i].num,&a[i].ei,&a[i].ti);
                time.push_back(a[i].si);
                time.push_back(a[i].ei);
                int tmp = a[i].num*a[i].ti;
                count+=tmp;
                add_Node(s,i,tmp);
            }
            sort(time.begin(),time.end());
            for(i=1;i<=n;i++)
            {
                for(j=0;j<(time.size()-1);j++)
                {
                    if(a[i].si<=time[j] && a[i].ei>=time[j+1]){
                        add_Node(i,n+j+1,inf);
                        //printf("-%d ",time[j]);
                    }
                }
            }
            for(i=0;i<(time.size()-1);i++)
                add_Node(n+i+1,t,(time[i+1]-time[i])*m);
            int ans=dinci(s,t);
            //printf("%d\n",ans);
            if(ans==count)
                printf("Yes\n");
            else
                printf("No\n");
            for(i=0;i<=t;i++)
                v[i].clear();
            e.clear();time.clear();
        }
        return 0;
    }

[hdoj 2883 kebab]: http://acm.hdu.edu.cn/showproblem.php?pid=2883
[Link 1]: http://blog.csdn.net/y990041769/article/details/38780391
[Center]: /images/20220810/8ffa223d6551464d9308ea5b45b5feff.png
[Image 1]: