[hdu6437]Problem L. Videos

题目大意：有$n$个小时，有$m$个节目（每种节目都有类型$0/1$），有$k$个人，一个人连续看相同类型的节目会扣$w$快乐值。

每一种节目有都一个播放区间$[l,r]$。每个人同一时间只能看一个节目，第$i$个节目只能一个人看，看完可以获得快乐$val_i$。问最多可以获得多少快乐？

题解：最大费用最大流，为了保证每个影片只被一个人观看，将其拆为入点和出点，入点和出点之间连一条容量为$1$，花费为$0$的边。

建一个源点$ST$和次源点$st$。从$ST$向$st$建一条容量为$k$，花费为$0$的边，表示有$k$个人可以看影片。

从$st$点向每个入点连一条容量为$1$，花费为$val_i$的边，若两个影片的时间不相交（$T_u \leqslant S_v$），那么在$u$到$v$之间建一条容量为$1$，花费为$val_v$的边；若$u,v$属性相同则花费为$val_v-W$。

最后将每个出点向汇点连一条容量为$1$，花费为$0$的边。

卡点：1.不知道为啥数组开小（计算出来不会锅）

　　 2.换电脑的时候代码未保存，把一份错误代码复制了过去（调了我一天）

C++ Code：

#include <cstdio>

#include <cstring>

#define maxn 1010

#define maxm 50100

const int inf = 0x3f3f3f3f;

int Tim;

int n, m, K, W, st, ed;

struct node {

	int S, T, w, ty;

} s[maxn];

int q[maxn], h, t;

int d[maxn], pre[maxn];

bool vis[maxn];

int head[maxn], cnt = 2;

struct Edge {

    int to, nxt, w, cost;

} e[maxm << 1];

void add(int a, int b, int c, int d) {

    e[cnt] = (Edge) {b, head[a], c, d}; head[a] = cnt;

    e[cnt ^ 1] = (Edge) {a, head[b], 0, -d}; head[b] = cnt ^ 1;

    cnt += 2;

}

inline int min(int a, int b) {return a < b ? a : b;}

bool spfa() {

    for (int i = st; i <= ed; i++) d[i] = -inf;

    d[q[h = t = 0] = st] = 0;

    while (h <= t) {

        int u = q[h++];

        vis[u] = false;

        for (int i = head[u]; i; i = e[i].nxt) {

            int v = e[i].to;

            if (e[i].w && d[v] < d[u] + e[i].cost) {

                d[v] = d[u] + e[i].cost;

                pre[v] = i;

                if (!vis[v]) {

                    q[++t] = v;

                    vis[v] = true;

                }

            }

        }

    }

    return d[ed] != -inf;

}

int update() {

    int ans, mf = inf;

    for (int i = pre[ed]; i; i = pre[e[i ^ 1].to]) mf = min(mf, e[i].w);

    ans = mf * d[ed];

    for (int i = pre[ed]; i; i = pre[e[i ^ 1].to]) e[i].w -= mf, e[i ^ 1].w += mf;

    return ans;

}

void MCMF() {

    int ans = 0;

    while (spfa()) ans += update();

    printf("%d\n", ans);

}

int main() {

	scanf("%d", &Tim);

	while (Tim --> 0) {

	    scanf("%d%d%d%d", &n, &m, &K, &W);

	    st = 0; ed = m + 1 << 1;

	    add(st, 1, K, 0);

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

	        scanf("%d%d%d%d", &s[i].S, &s[i].T, &s[i].w, &s[i].ty);

	        add(i << 1, i << 1 | 1, 1, 0);

	        add(1, i << 1, 1, s[i].w);

	        add(i << 1 | 1, ed, 1, 0);

	    }

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

	    	for (int j = 1; j <= m; j++) {

	    		if (i != j && s[i].T <= s[j].S) add(i << 1 | 1, j << 1, 1, (s[i].ty == s[j].ty) ? s[j].w : s[j].w - W);

			}

		}

	    MCMF();

	    if (Tim) memset(head, 0, sizeof head), cnt = 2;

	}

    return 0;

}

巴特西

[hdu6437]Problem L. Videos

最新文章

热门文章