hdu - 3572 - Task

矫情吗；* 2021-12-13 23:43 177阅读 0赞

题意：有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][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;
    }

转载于:https://www.cnblogs.com/james1207/p/3299382.html

[http_acm.hdu.edu.cn_showproblem.php_pid_3572]: http://acm.hdu.edu.cn/showproblem.php?pid=3572