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 0Sample Output
2000
1990Source
2018 Multi-University Training Contest 10
Recommend
chendu
链接
http://acm.hdu.edu.cn/showproblem.php?pid=6437
题意
有0和1两种不同类型的视频，每个视频有开始时间s结束时间t和看完后能获得的愉悦值w，现在安排k个人看电影，规则如下：
- 一个人在一个时间内只能看一个视频，如果视频之间的播放时间不重合，那么它可以连续看多个视频
- 每个视频只允许一个人观看
- 一个人连续观看相同类型的视频会减去W的愉悦值，类似'A-A-A-B-B'这种就会减去3W愉悦值，但是交替观看两种不同类型的就不会失去愉悦值
现问k个人一共最多能获得多少愉悦值。
题解
比赛的时候和队友讨论，确实了是网络流模型，也确定了是最大费用最大流，也想到了把电影拆点分析，但是对于连续观看相同类型的视频会减去W的愉悦值不知道该怎么转化，所以图模型没有建立起来，GG。
赛后看群里有个老哥BlockChanZJ说：
电影拆成出点入点，入点向出点建立容量1，费用-w的边，电影之间，如果不重合，出点向入点建立费用W的边，然后起点限制流量k，跑最小费用就可以了。
然后我按照这个写好之后跑费用流时会陷入死循环，一直没改出来。后面去网上看了一下别人的代码，发现我有个地方写错了，在视频之间建边的时候，判断不重合的条件应该只有(node[j].s >= node[i].t)，而我一开始写的是(node[j].s >= node[i].t || node[i].s >= node[j].t)，所以就陷入死循环了。
本来的的意思应该是如果后面的视频与当前的视频不重合（时间不冲突），那么我们就把当前视频和后面的视频连边，而我还加了一个当前的视频与之前已经看过的视频不重合也连边，于是就出现了问题...改了之后一发过了。
做法就是BlockChanZJ老哥说的，我是建立了两个源点和两个汇点，源点和次源点之间容量为K，费用为0，次源点和每个视频的起点之间容量为1，费用为0，每个视频的终点和次汇点之间容量为1，费用为0，次汇点和汇点之间容量为K，费用为0。
可以根据样例画一个图出来，然后就很清晰了。
代码
| Status | Accepted |
|---|---|
| Time | 156ms |
| Memory | 1716kB |
| Length | 3397 |
#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 head[maxn], pre[maxn], dis[maxn];
int n, m, tot, N;
bool vis[maxn];
void init()
{
memset(head, -1, sizeof(head));
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].next = head[u];
head[u] = tot++;
edge[tot].to = u;
edge[tot].cap = 0;
edge[tot].cost = -cost;
edge[tot].flow = 0;
edge[tot].next = head[v];
head[v] = tot++;
}
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 星期四
哇发现了自己
优秀！