# HDU6437 Problem L.Videos（最大费用最大流）

## Problem L.Videos

• Time Limit: 4000/2000 MS (Java/Others)
• Memory Limit: 524288/524288 K (Java/Others)
• Total Submission(s): 349
• Accepted Submission(s): 168

### Problem Description

C-bacteria takes charge of two kinds of videos: ’The Collection of Silly Games’ and ’The Collection of Horrible Games’.
For simplicity’s sake, they will be called as videoA and videoB.
There are some people who want to watch videos during today, and they will be happy after watching videos of C-bacteria.
There are n hours a day, m videos are going to be show, and the number of people is K.
Every video has a type(videoA or videoB), a running time, and the degree of happi- ness after someone watching whole of it.
People can watch videos continuous(If one video is running on 2pm to 3pm and another is 3pm to 5pm, people can watch both of them).
But each video only allows one person for watching.
For a single person, it’s better to watch two kinds to videos alternately, or he will lose W happiness.
For example, if the order of video is ’videoA, videoB, videoA, videoB, …’ or ’B, A, B, A, B, …’, he won’t lose happiness; But if the order of video is ’A, B, B, B, A, B, A, A’, he will lose 3W happiness.
Now you have to help people to maximization the sum of the degree of happiness.

### Input

Multiple query.
On the first line, there is a positive integer T, which describe the number of data. Next there are T groups of data.
for each group, the first line have four positive integers n, m, K, W : n hours a day, m videos, K people, lose W happiness when watching same videos).
and then, the next m line will describe m videos, four positive integers each line S, T, w, op : video is the begin at S and end at T, the happiness that people can get is w, and op describe it’s tpye(op=0 for videoA and op=1 for videoB).
There is a blank line before each groups of data.
T<=20, n<=200, m<=200, K<=200, W<=20, 1<=S<T<=n, W<=w<=1000, op=0 or op=1

### Output

Your output should include T lines, for each line, output the maximum happiness for the corresponding datum.

### Sample Input

2
10 3 1 10
1 5 1000 0
5 10 1000 1
3 9 10 0
10 3 1 10
1 5 1000 0
5 10 1000 0
3 9 10 0

### Sample Output

2000
1990

### Source

2018 Multi-University Training Contest 10

chendu

### 链接

http://acm.hdu.edu.cn/showproblem.php?pid=6437

### 题意

• 一个人在一个时间内只能看一个视频，如果视频之间的播放时间不重合，那么它可以连续看多个视频
• 每个视频只允许一个人观看
• 一个人连续观看相同类型的视频会减去W的愉悦值，类似'A-A-A-B-B'这种就会减去3W愉悦值，但是交替观看两种不同类型的就不会失去愉悦值

### 代码

StatusAccepted
Time156ms
Memory1716kB
Length3397
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 510; // 点数
const int maxm = 10010; // 边数
const int inf = 0x3f3f3f3f;

struct Edge
{
int to, next, cap, flow, cost;
}edge[maxm<<2];

int n, m, tot, N;
bool vis[maxn];

void init()
{
tot = 0;
}

void addedge(int u, int v, int cap, int cost) // 链式前向星存图
{
edge[tot].to = v;
edge[tot].cap = cap;
edge[tot].cost = cost;
edge[tot].flow = 0;
edge[tot].to = u;
edge[tot].cap = 0;
edge[tot].cost = -cost;
edge[tot].flow = 0;
}

bool spfa(int s, int t) // spfa寻找最小费用增广路
{
queue <int> Q;
for (int i = 0; i <= N; ++i) // 注意N表示所有点数
{
dis[i] = inf;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
Q.push(s);
while (!Q.empty())
{
int u = Q.front();
Q.pop();
vis[u] = false;
for (int i = head[u]; i != -1; 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] == -1)
return false;
return true;
}

int minCostMaxflow(int s, int t, int &mincost) // 计算费用
{
int maxflow = 0;
mincost = 0;
while (spfa(s, t))
{
int Min = inf;
for (int i = pre[t]; i != -1; i = pre[edge[i^1].to]) // 每次增加的流量
Min = min(Min, edge[i].cap - edge[i].flow);
for (int i = pre[t]; i != -1; i = pre[edge[i^1].to])
{
edge[i].flow += Min;
edge[i^1].flow -= Min;
mincost += edge[i].cost * Min;
}
maxflow += Min;
}
return maxflow;
}

struct Node
{
int s, t, w, id;
}node[maxn<<2];

int main()
{
//    freopen("/Users/taifu/Codes/NOW/data.in", "r", stdin);
//    freopen("/Users/taifu/Codes/NOW/data.out","w",stdout);
int T, s, t, K, W;
scanf("%d", &T);
while (T--)
{
scanf("%d%d%d%d", &n, &m, &K, &W);
init();
s = 0, t = 2 * m + 1;
for (int i = 1; i <= m; ++i)
scanf("%d%d%d%d", &node[i].s, &node[i].t, &node[i].w, &node[i].id);
for (int i = 1; i <= m; ++i)
addedge(i, m + i, 1, -node[i].w);
addedge(s, 2 * m + 2, K, 0); // 超级源和起点，容量为K，费用为0
addedge(2 * m + 3, t, K, 0); // 终点和超级汇，容量为K，费用为0
N = 2 * m + 4;
for (int i = 1; i <= m; ++i)
{
addedge(2 * m + 2, i, 1, 0); // 起点和每个视频的入点
addedge(m + i, 2 * m + 3, 1, 0); // 每个视频的出点和终点
for (int j = 1; j <= m; ++j)
{
if ((i != j) && (node[j].s >= node[i].t)) // 如果播放时间不重合
{
if (node[i].id == node[j].id) // 同类型
addedge(m + i, j, 1, W);
else
addedge(m + i, j, 1, 0);
}
}
}
int maxflow, mincost = 0;
maxflow = minCostMaxflow(s, t, mincost);
printf("%d\n", -mincost); // 相反数
}
return 0;
}

ε=(´ο｀*)))唉，拖后腿了...

The end.
2018-08-23 星期四

1. BlockChanZJ

哇发现了自己

1. @BlockChanZJ优秀！