补题：2018hdu多校暑期训练第十场L:Videos（hdu-6437) （最大费用流）

红太狼 2022-05-15 02:48 179阅读 0赞

题目链接：  
[hdu-6437][]

题目大意：  
给定一天n个时间点，m个电影，电影有两种类型，一个电影只能被一个人观看，k个人，一个人不同同时看两部电影；看完一部电影会获得相应的快乐值，如果连续看相同类型的电影，会减去w的快乐值，求k个人最大快乐值和

解题思路：  
题解已经讲得很明白了，最关键的就是抽象出题目的模型，建好网络图，直接上最小费用最大流的板子就好，因为这里要求最大费用流，所有我们需要把边的花费取负，最后结果再取负就是答案了

可参考这个建图，测试样例1的网络图(图片摘自博客：[图片来源][Link 1] ）  
![这里写图片描述][70]

一些解释：因为源点流量不是无穷大，所以需要建立次源点，其2，因为我们观看完一场电影会获得快乐值，所以需要拆点。应该很好理解的，需要补补网络流了，告辞！

AC代码：

#include <bits/stdc++.h>
    using namespace std;
    
    const int MAXN = 200+233;
    const int MAXM = 200+233;
    const int INF = 0x3f3f3f3f;
    
    struct node{
        int u, v, w, c, next;
        node(){}
        node(int _u, int _v, int _w, int _c, int _next):u(_u),v(_v),w(_w),c(_c),next(_next){}
    }edge[MAXM*1000];
    
    struct mov{
        int st, en, w, op;
    }mov[MAXM];
    
    int n, m, K, W, cnt, source, _end, source2;
    int Next[MAXM*1000], vis[MAXM*1000], dis[MAXM*1000],pre[MAXM*1000];
    
    void addedge(int u, int v, int w, int c){
        edge[cnt] = node(u,v,w,c,Next[u]);
        Next[u] = cnt++;
        edge[cnt] = node(v,u,0,-c,Next[v]);
        Next[v] = cnt++;
    }
    
    bool spfa(){  //找最短增广路
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<MAXM*1000; ++i) dis[i] = INF;
        int l = 0, r = 0;
        dis[source] = 0;
        vis[source] = 1;
        queue<int> q;
        q.push(source);
        while(!q.empty()){
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for(int i = Next[u]; i!=-1; i=edge[i].next){
                int v = edge[i].v, w = edge[i].w, c = edge[i].c;
                if(w > 0 && dis[v] > dis[u] + c){
                    dis[v] = dis[u] + c;
                    pre[v] = i;
                    if(!vis[v]){
                        q.push(v);
                        vis[v] = 1;
                    }
                }
            }
        }
        if(dis[_end] != INF) return true;
        return false;
    }
    int MVCF(){ //更新网络图
        int full = 0;
        int cost = 0;
        while(spfa()){
            int Min = INF;
            for(int i = _end; i != source; i=edge[pre[i]].u) {
                Min = min(Min, edge[pre[i]].w);
            //    cout<<i<<endl;
            }
            for(int i= _end; i!=source; i=edge[pre[i]].u){
                edge[pre[i]].w -= Min;
                edge[pre[i]^1].w += Min;
            }
            cost += Min*dis[_end];
            full += Min;
        }
        return cost;
    }
    
    int main(int argc, char const *argv[])
    {
        int t;
        cin>>t;
        while(t--){
            memset(Next, -1, sizeof(Next));
            cnt = 0;
            scanf("%d%d%d%d",&n,&m,&K,&W);
            source = 0, _end = 2*m+2, source2 = 2*m+1; //源点，汇点，次源点
            addedge(source, source2, K, 0);
            for(int i=1; i<=m; ++i){
                scanf("%d%d%d%d",&mov[i].st, &mov[i].en, &mov[i].w, &mov[i].op);
                addedge(i, i+m, 1, -mov[i].w);
                addedge(source2, i, 1, 0);
                addedge(i+m, _end, 1, 0);
            }
    
            for(int i=1; i<=m; ++i){
                for(int j=1; j<=m; ++j){
                    if(i==j) continue;
                    if(mov[j].st >= mov[i].en){
                        addedge(i+m, j, 1, (mov[i].op==mov[j].op? W : 0));
                    }
                }
            }
    
            printf("%d\n",-MVCF());
        }
        return 0;
    }

[hdu-6437]: http://acm.hdu.edu.cn/showproblem.php?pid=6437
[Link 1]: http://www.cnblogs.com/xcantaloupe/p/9519617.html
[70]: /images/20220515/f429fb2bfdb749b990c9abdeaa50ecb0.png