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)。     ——>>建圖思路原來是這樣子：設一個超級源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;  
}  

#include <cstdio>  
#include <queue>  
#include <algorithm>  
#include <cstring>  
  
using namespace std;  
  
const int maxn = 1000 + 10;  
const int maxm = 502000 + 10;  
const int INF = 0x3f3f3f3f;  
  
int head[maxn], nxt[maxm], ecnt, v[maxm], flow[maxm], cap[maxm];  
bool flag[maxn];  
int N, M;  
  
struct Dinic{  
    int m, s, t;  
    int d[maxn], cur[maxn];  
    bool vis[maxn];  
  
    Dinic(){  
        memset(head, -1, sizeof(head));  
        ecnt = 0;  
    }  
  
    void addEdge(int uu, int vv, int ca){  
        v[ecnt] = vv; cap[ecnt] = ca; flow[ecnt] = 0; nxt[ecnt] = head[uu]; head[uu] = ecnt; ecnt++;  
        v[ecnt] = uu; cap[ecnt] = 0; flow[ecnt] = 0; nxt[ecnt] = head[vv]; head[vv] = ecnt; ecnt++;  
    }  
  
    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();  
            for(int e = head[u]; e != -1; e = nxt[e]){  
                if(!vis[v[e]] && cap[e] > flow[e]){  
                    d[v[e]] = d[u] + 1;  
                    vis[v[e]] = 1;  
                    qu.push(v[e]);  
                }  
            }  
        }  
        return vis[t];  
    }  
  
    int dfs(int u, int a){  
        if(u == t || a == 0) return a;  
        int f, Flow = 0;  
        for(int e = cur[u]; e != -1; e = nxt[e]){  
            cur[u] = e;  
            if(d[v[e]] == d[u] + 1 && (f = dfs(v[e], min(a, cap[e]-flow[e]))) > 0){  
                flow[e] += f;  
                flow[e^1] -= 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()){  
            memcpy(cur, head, sizeof(head));  
            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;  
}