hdu - 3572 - Task

题意：有N个作业，M台机器，每个作业1天只能同1台机器运行，每台机器1天只能运行1个作业，第i个作业需要pi天完成，且只能从Si到Ei中选Pi天，问能否完成所有作业(T <= 20, N<=500, M<=200, 1 <= Pi, Si, Ei <= 500)。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3572

——>>建图思路原来是这样子：设一个超级源s，每个作业为1个结点，从s往每个作业分别连1条边，容量为完成该作业所需的时间，那么从s发出满流时，就是作业所需天数，最后就看最大流是否为满流即可；作业可选择的天也分别作为1个结点，每个作业分别向其可选择的天连1条边，容量为1（因为每个作业1天只能同1台机器运行，每台机器1天只能运行1个作业）；最后，所有可选择的天分别向超级汇t连1条边，容量为M（因为每天最多只有M台机器）～ok～

#include <cstdio>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

using namespace std;

const int maxn = 1000 + 10;

const int INF = 0x3f3f3f3f;

int N, M;

bool flag[maxn];

struct Edge{

    int u, v, cap, flow;

    Edge(int u = 0, int v = 0, int cap = 0, int flow = 0):

    u(u), v(v), cap(cap), flow(flow){}

};

struct Dinic{

    vector<Edge> edges;

    vector<int> G[maxn];

    int m, s, t;

    int d[maxn], cur[maxn];

    bool vis[maxn];

    void addEdge(int u, int v, int cap){

        edges.push_back(Edge(u, v, cap, 0));

        edges.push_back(Edge(v, u, 0, 0));

        m = edges.size();

        G[u].push_back(m-2);

        G[v].push_back(m-1);

    }

    bool bfs(){

        d[s] = 0;

        memset(vis, 0, sizeof(vis));

        queue<int> qu;

        qu.push(s);

        vis[s] = 1;

        while(!qu.empty()){

            int u = qu.front(); qu.pop();

            int sz = G[u].size();

            for(int i = 0; i < sz; i++){

                Edge& e = edges[G[u][i]];

                if(!vis[e.v] && e.cap > e.flow){

                    d[e.v] = d[u] + 1;

                    vis[e.v] = 1;

                    qu.push(e.v);

                }

            }

        }

        return vis[t];

    }

    int dfs(int u, int a){

        if(u == t || a == 0) return a;

        int f, flow = 0;

        int sz = G[u].size();

        for(int i = cur[u]; i < sz; i++){

            Edge& e = edges[G[u][i]];

            cur[u] = i;

            if(d[e.v] == d[u] + 1 && (f = dfs(e.v, min(a, e.cap-e.flow))) > 0){

                e.flow += f;

                edges[G[u][i]^1].flow -= f;

                flow += f;

                a -= f;

                if(!a) 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;

    }

};

int main()

{

    int T, P, S, E, kase = 1;

    scanf("%d", &T);

    while(T--){

        Dinic din;

        scanf("%d%d", &N, &M);

        memset(flag, 0, sizeof(flag));

        int sum = 0;

        for(int i = 1; i <= N; i++){

            scanf("%d%d%d", &P, &S, &E);

            din.addEdge(0, i, P);

            for(int j = S; j <= E; j++){

                din.addEdge(i, N+j, 1);

                if(!flag[N+j]){

                    din.addEdge(N+j, 1001, M);

                    flag[N+j] = 1;

                }

            }

            sum += P;

        }

        if(din.Maxflow(0, 1001) == sum) printf("Case %d: Yes\n\n", kase++);

        else printf("Case %d: No\n\n", kase++);

    }

    return 0;

}

巴特西

hdu - 3572 - Task

最新文章

热门文章