HDU-6437 Videos

HDU-6437

题意：一天有n个小时，现在有m场电影，每场电影有一个愉悦值，有k个人，电影分2种类型A， B，并且每一场电影只能一个人看，一个人可以看无数次电影，只要时间足够，但是连续看同一种电影会减少愉悦值W点。现在要求所有人总的愉悦值加起来最大。

题解：

网络流建图，先把每个点拆成2个点， u 和 u‘ ，在u和u’中间连一条流量为1，费用为0的边，现在我们规定一个点的复制点只能和本体链接，只能由复制点往外流，然后别的点流入只能留到本体。

也就是假设存在 u， v2个点，这2个点之间可以存在边且为u->v 那么连线方式就为 u -> u' -> v -> v'。

因为每个电影看的人最多是1，所以 u - > u' 的流量为1。

s -> s'的流量为k。

然后我们把s‘和所有的电影建边流量为1，花费为电影获得的愉悦值

然后把所有电影与t建边流量为1，花费为0

然后我们把看完一场电影之后可以去看另一场电影的2个点建边，花费为下一次电影的愉悦值 - （是否为同一种类电影）* W。

由于是需要最大的愉悦值，我们把花费取反，然后跑费用流。最后把答案取反。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const LL mod =  (int)1e9+;

 const int N = 1e5;

 const int M = ;

 int head[M], to[N], ct[N], w[N], nt[N];

 int d[M], vis[M];

 int pre[M], id[N];

 int n, m, s, t, tot;

 void add(int u, int v, int val, int cost){

     to[tot] = v;

     ct[tot] = -cost;

     w[tot] = val;

     nt[tot] = head[u];

     head[u] = tot++;

     to[tot] = u;

     ct[tot] = cost;

     w[tot] = ;

     nt[tot] = head[v];

     head[v] = tot++;

 }

 void init(){

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

     tot = ;

 }

 int spfa(){

     queue<int> q;

     memset(d, INF, sizeof(d));

     memset(vis, , sizeof(vis));

     memset(pre, -, sizeof(vis));

     d[s] = ;

     q.push(s);

     while(!q.empty()){

         int u = q.front(); q.pop();

         vis[u] = ;

         for(int i = head[u]; ~i; i = nt[i]){

             if(w[i] >  && d[to[i]] > d[u] + ct[i]){

                 d[to[i]] = d[u] + ct[i];

                 pre[to[i]] = u;

                 id[to[i]] = i;

                 if(!vis[to[i]]){

                     vis[to[i]] = ;

                     q.push(to[i]);

                 }

             }

         }

     }

     return d[t] < INF;

 }

 int MaxFlow(){

     int Mi = INF;

     int sum = ;

     while(spfa()){

         Mi = INF;

         for(int i = t; i != s; i = pre[i])

             Mi = min(Mi, w[id[i]]);

         for(int i = t; i != s; i = pre[i]){

             w[id[i]] -= Mi;

             w[id[i]^] += Mi;

         }

         sum += d[t];

     }

     return sum;

 }

 struct Node{

     int l, r, t, op;

     bool operator < (const Node & x) const {

         return l < x.l;

     }

 }A[N];

 int main(){

     int T, n, m, k, lost;

     scanf("%d", &T);

     while(T--){

         scanf("%d%d%d%d", &n, &m, &k, &lost);

         init();

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

             scanf("%d%d%d%d", &A[i].l, &A[i].r, &A[i].t, &A[i].op);

         sort(A+, A++m);

         s = , t =  * m+;

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

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

                 if(A[i].r <= A[j].l){

                     add(m + i, j, , A[j].t - lost*(A[i].op == A[j].op));

                 }

             }

         }

         add(s,  * m + , k, );

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

             add( * m + , i, , A[i].t);

             add(i, m + i, , );

             add(m + i, t, , );

         }

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

     }

     return ;

 }

巴特西

HDU-6437 Videos

最新文章

热门文章