『算法-ACM 竞赛-图论』网络流最大流 HDU3572TaskSchedule（限流建图，超级源汇）

图论–网络流–最大流 HDU 3572 Task Schedule（限流建图，超级源汇）

Problem Description

Our geometry princess XMM has stoped her study in computational geometry to concentrate on her newly opened factory. Her factory has introduced M new machines in order to process the coming N tasks. For the i-th task, the factory has to start processing it at or after day Si, process it for Pi days, and finish the task before or at day Ei. A machine can only work on one task at a time, and each task can be processed by at most one machine at a time. However, a task can be interrupted and processed on different machines on different days.
Now she wonders whether he has a feasible schedule to finish all the tasks in time. She turns to you for help.

Input

On the first line comes an integer T(T<=20), indicating the number of test cases.

You are given two integer N(N<=500) and M(M<=200) on the first line of each test case. Then on each of next N lines are three integers Pi, Si and Ei (1<=Pi, Si, Ei<=500), which have the meaning described in the description. It is guaranteed that in a feasible schedule every task that can be finished will be done before or at its end day.

Output

For each test case, print “Case x: ” first, where x is the case number. If there exists a feasible schedule to finish all the tasks, print “Yes”, otherwise print “No”.

Print a blank line after each test case.

Sample Input

2

4 3

1 3 5

1 1 4

2 3 7

3 5 9

2 2

2 1 3

1 2 2

Sample Output

Case 1: Yes

Case 2: Yes

每个机器每台只能执行一个任务，每个任务在同一时段也只能被一台机执行。 给每个任务的开始时间和截止时间，和持续天数。最多给 500 天。

建立超级源点，源点到每个任务的流量为持续时间，每天到超级汇点的流量为 M，这样能限制流量，即每天只能只能有 M 机器工作，然后每个任务到日期内的每一天设置流量为 1，限制流量，即每天这个任务最多被一台机器干。欧克收工。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define INF 1e9
using namespace std;
const int maxn =1000+10;

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];
    bool vis[maxn];
    int cur[maxn];
    int d[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 full_flow;

int main()
{
    int T; scanf("%d",&T);
    for(int kase=1;kase<=T;++kase)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        full_flow=0;
        int src=0,dst=500+n+1;
        DC.init(500+2+n,src,dst);
        bool vis[maxn];//表示第i天是否被用到
        memset(vis,0,sizeof(vis));

        for(int i=1;i<=n;++i)
        {
            int P,S,E;
            scanf("%d%d%d",&P,&S,&E);
            DC.AddEdge(src,500+i,P);
            full_flow += P;
            for(int j=S;j<=E;++j)
            {
                DC.AddEdge(500+i,j,1);
                vis[j]=true;
            }
        }

        for(int i=1;i<=500;++i)if(vis[i])//被任务覆盖的日子才添加边
            DC.AddEdge(i,dst,m);
        printf("Case %d: %s\n\n",kase,DC.max_flow()==full_flow?"Yes":"No");
    }
    return 0;
}