[HDU][ACM]2883 kebab
海胖子 - 2014/05/05题目链接
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 - 海胖博客