HDU - 6437 Problem L.Videos 2018 Multi-University Training Contest 10 (最小费用最大流)

题意：M个影片，其属性有开始时间S，结束时间T，类型op和权值val。有K个人，每个人可以看若干个时间不相交的影片，其获得的收益是这个影片的权值val，但如果观看的影片相邻为相同的属性，那么收益要减少W。每个影片只能被一个人看。求所有人能获得的收益值之和的最大值。

分析：因为人数不定，所以贪心和dp的思路被否定了。1对多的带权匹配，求最大权，这种问题显然KM是解决不了的，那么只能是最小费用最大流了。而这题要求的是最大收益，那么建负权边即可。

为了保证每个影片只被一个人观看，将其拆为入点和出点，入点和出点之间连一条容量为1，花费为0的边，网络流建图的基本操作。

首先虚拟一个源点st和源点big。从big向st建一条容量为K，花费为0的边，表示有K个人可以进行接下来选影片的操作。

从st点向每个入点连一条容量为1，花费为-val[i]的边，表示每个影片都可以作为某个人最先观看的影片。

若两个影片的时间不相交（u->T <= v->S），那么在u到v之间建一条容量为1，花费为-val[v]的边；若u,v属性相同则花费为-val[v]+W。

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

跑出的最小花费取反就是所求答案。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = ;

const int MAXM = ;

const int INF = 0x3f3f3f3f;

struct Edge{

    int to, next, cap, flow, cost;

} edge[MAXM];

int head[MAXN], tol;

int pre[MAXN], dis[MAXN];

bool vis[MAXN];

int N;                  //0~N-1的点数

void init(int n)

{

    N = n;

    tol = ;

    memset(head, -, sizeof(head));

}

void addedge(int u, int v, int cap, int cost)

{

    edge[tol].to = v;

    edge[tol].cap = cap;

    edge[tol].cost = cost;

    edge[tol].flow = ;

    edge[tol].next = head[u];

    head[u] = tol++;

    edge[tol].to = u;

    edge[tol].cap = ;

    edge[tol].cost = -cost;

    edge[tol].flow = ;

    edge[tol].next = head[v];

    head[v] = tol++;

}

bool spfa(int s, int t){

    queue<int> q;

    for (int i = ; i < N; i++){

        dis[i] = INF;

        vis[i] = false;

        pre[i] = -;

    }

    dis[s] = ;

    vis[s] = true;

    q.push(s);

    while (!q.empty()){

        int u = q.front();

        q.pop();

        vis[u] = false;

        for (int i = head[u]; i != -; i = edge[i].next){

            int v = edge[i].to;

            if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost){

                dis[v] = dis[u] + edge[i].cost;

                pre[v] = i;

                if (!vis[v]){

                    vis[v] = true;

                    q.push(v);

                }

            }

        }

    }

    if (pre[t] == -) return false;

    else  return true;

}

int minCostMaxflow(int s, int t, int &cost){

    int flow = ;

    cost = ;

    while (spfa(s, t)){

        int Min = INF;

        for (int i = pre[t]; i != -; i = pre[edge[i ^ ].to]){

            if (Min > edge[i].cap - edge[i].flow)

                Min = edge[i].cap - edge[i].flow;

        }

        for (int i = pre[t]; i != -; i = pre[edge[i ^ ].to]){

            edge[i].flow += Min;

            edge[i ^ ].flow -= Min;

            cost += edge[i].cost * Min;

        }

        flow += Min;

    }

    return flow;

}

int n,M,K,W;

struct Node{

    int s,t,op,val;

}pt[MAXN];

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    int T; scanf("%d",&T);

    while(T--){

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

        int st = ,big =*M+;

        int ed = big+;

        init(*M+);

        addedge(big,st,K,);

        for(int i=;i<=M;++i){

            scanf("%d%d%d%d",&pt[i].s,&pt[i].t, &pt[i].val, &pt[i].op);

            addedge(st,i,,-pt[i].val);

            addedge(i+M,ed,,);

            addedge(i,i+M,,);

        }

        for(int i=;i<=M;++i){

            for(int j=;j<=M;++j){

                if(i==j) continue;

                if(pt[i].t<=pt[j].s){

                    if(pt[i].op^pt[j].op){

                        addedge(i+M,j,,-pt[j].val);

                    }

                    else{

                        addedge(i+M,j,,-(pt[j].val-W));

                    }

                }

            }

        }

        int res;

        minCostMaxflow(big,ed,res);

        printf("%d\n",-res);

    }

    return ;

}

巴特西

HDU - 6437 Problem L.Videos 2018 Multi-University Training Contest 10 (最小费用最大流)

最新文章

热门文章