题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2883

题解

网络流之最大流 SAP算法+GAP优化

代码 

/*
 * Author: Haipz
 * School: HDU
 * File Name: 2883.cpp
 */
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cfloat>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

const int N = 200, M = 1e3, Ni = 50, Ti = 50, Si = 1e6, Ei = 1e6;
struct edge {
    int v, w;
    edge *next, *opt;
} f[N*N*2 + N + N*2 + 5], *link[N*3 + 5];
int h[N*3 + 5], gap[N*3 + 5];
struct node {
    int s, n, e, t;
} data[N + 5];
int a[N*2 + 5];

void addEdge(int &k, int u, int v, int w) {
    ++k;
    f[k].v = v, f[k].w = w, f[k].next = link[u];
    f[k].opt = f + k + 1, link[u] = f + k;
    ++k;
    f[k].v = u, f[k].w = 0, f[k].next = link[v];
    f[k].opt = f + k - 1, link[v] = f + k;
    return;
}

int aug(int u, int s, int t, int n, int flow) {
    if (u == t) return flow;
    int l = flow, tmp = n - 1;
    for (edge *p = link[u]; p; p = p->next) {
        if (h[u] == h[p->v] + 1 && p->w) {
            int f = aug(p->v, s, t, n, min(l, p->w));
            l -= f, p->w -= f, p->opt->w += f;
            if (l == 0 || h[s] == n) return flow - l;
        }
        if (p->w > 0 && h[p->v] < tmp) tmp = h[p->v];
    }
    if (l == flow) {
        --gap[h[u]];
        if (gap[h[u]] == 0) h[s] = n;
        else h[u] = tmp + 1, ++gap[h[u]];
    }
    return flow - l;
}

int sap(int s, int t, int n) {
    int ans = 0;
    memset(h, 0, sizeof(h));
    memset(gap, 0, sizeof(gap));
    while (h[s] < n) ans += aug(s, s, t, n, INT_MAX);
    return ans;
}

int main(){
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(link, NULL, sizeof(link));
        int sum = 0, cnt = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d%d%d", &data[i].s, &data[i].n, &data[i].e, &data[i].t);
            a[i*2 - 1] = data[i].s, a[i*2] = data[i].e, sum += data[i].n*data[i].t;
            addEdge(cnt, 0, i, data[i].n*data[i].t);
        }
        sort(a + 1, a + 1 + n*2);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j < n*2; ++j)
                if (data[i].s <= a[j] && data[i].e >= a[j + 1]) addEdge(cnt, i, n + j, INT_MAX);
        for (int j = 1; j < n*2; ++j) addEdge(cnt, n + j, n*3 + 1, (a[j + 1] - a[j])*m);
        if (sum == sap(0, n*3 + 1, n*3 + 2)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

转载保留版权：http://haipz.com/blog/i/2071 - 海胖博客