HDU4560 我是歌手 <二分+网络流>

Posted on Symbols count in article: 1.4k Reading time ≈ 5 mins.

Problem

我是歌手

Time  Limit:  2000  MS\mathrm{Time\;Limit:\;2000\;MS}
Memory  Limit:  32768  KB\mathrm{Memory\;Limit:\;32768\;KB}

Description

20132013年一开始，一档音乐节目“我是歌手”就惊艳了大家一回。闲话少说，现在，你成为了这档节目的总导演，你的任务很简单，安排每一期节目的内容。
现在有NN个歌手，MM种歌曲流派（RockRock，PopPop之类），每个歌手都有自己擅长的流派领域，这些资料都已整理。你的工作是，安排尽可能多场的演唱比赛。每一场比赛所有歌手都必须上场，为了提高收视率，每个人演唱的歌曲类型不能相同，即便一些歌手要被迫选择一些他们不擅长的。同时，为了展现全面性，在不同的演唱比赛上，每个歌手都会安排不同的歌曲流派。
但是问题是，对于任何一个歌曲流派的歌迷，如果超过KK个不擅长的歌手演唱了这种歌曲，他们就会表示不满，比如，发一些宣泄不满的帖子微博，为了表示观点挑起事端等等。你当然不希望这些事情与你的节目有关，在这个前提下，你可以任意安排尽可能多的比赛场次。

Input

输入第一行为TT，表示有TT组测试数据。
每组数据以四个数字NN，MM，LL，KK开始。LL表示有LL组擅长关系，接下来的LL行，每一行有两个数字AiA_i，BiB_i，表示歌手AiA_i擅长BiB_i类型的歌曲。

Output

对每组数据，先输出为第几组数据，然后输出最多比赛场次。

Sample Input

1
2
3
4
5
6
7
8
9
10
3
1 1 1 0
1 1
1 3 0 1
3 3 5 1
1 1
1 2
2 2
2 3
3 1

Sample Output

1
2
3
Case 1: 1
Case 2: 3
Case 3: 2

Explanation

1
2
3
对第三组样例，可以如此安排：
第一场三位歌手分别演唱(2,3,1)类型的歌曲，第二场分别演唱(1,2,3)。
这样只有类型3被不擅长的歌手演唱过1次，挑剔的歌迷观众还可以接受。

Hint

$1\le T \le 100 $
$1\le N \le M \le 74, 0 \le K \le N $
0≤L≤N×M0\le L \le N\times M
1≤Ai≤N,1≤Bi≤M1\le A_i \le N, 1 \le B_i \le M
相同关系不会重复出现

标签：带修主席树

Solution

挺好的一道二分+网络流二分+网络流套路建模题。

二分最多能安排的场次，得到当前答案进行判定。

首先，如果保证每个人唱每种流派最多仅一次，并且nn个流派均会被唱至少tanstans次，那么一定能找到一组解。这样就可以用最大流判定。
由于有“每个流派仅能有kk个不擅长的选手唱”，我们需要把每个流派又擅长的选手唱和不擅长的选手唱分开，而限制不擅长的选手的数量。可将每个流派拆成两个点，即第ii个流派StyleiStyle_i拆成StyleiStyle_i和Stylei′Style_i'。从StyleiStyle_i向擅长的选手连边，从Stylei′Style_i'向不擅长的选手连边，而由于从源点向StyleiStyle_i连有tanstans的边，因而所有可用流量都在StyleiStyle_i中，Stylei′Style_i'的流量需要限制，故要在StyleiStyle_i和Stylei′Style_i'间连KK的边来限制不擅长选手的数量。

建模总述：

S→Stylei(i∈[1,m]):Capacity=tansStylei→Stylei′(i∈[1,m]):Capacity=KStylei→Competitorj(Competitorj is good at Stylei):Capacity=1Stylei′→Competitorj(Competitorj is not good at Stylei):Capacity=1Competitorj→T(j∈[1,n]):Capacity=tans\begin{aligned} S &\to Style_i(i\in [1,m]):Capacity=tans\\ Style_i &\to Style_i'(i\in [1,m]):Capacity=K\\ Style_i &\to Competitor_j(Competitor_j\ is\ good\ at\ Style_i):Capacity=1\\ Style_i' &\to Competitor_j(Competitor_j\ is\ not\ good\ at\ Style_i):Capacity = 1\\ Competitor_j &\to T(j\in [1,n]):Capacity=tans\\ \end{aligned}

建模后跑最大流，看是否有MaxFlow=tans×nMaxFlow=tans\times n即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define MAX_N 1000
#define MAX_M 2000000
#define mid ((l+r)>>1)
#define INF 0x7f7f7f7f
using namespace std;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, k, f, s, t, cnt, d[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5];
struct node {int v, c, nxt;} E[MAX_M+5]; bool G[MAX_N+5][MAX_N+5];
void init() {cnt = s = 0, t = 3*m+1, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que;	que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow;	int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;	return ret;
}
void cpy() {for (int i = s; i <= t; i++) cr[i] = pr[i];}
void rec() {for (int i = s; i <= t; i++) pr[i] = cr[i];}
int Dinic() {int ret = 0;    cpy();	while (BFS()) ret += DFS(s, INF), rec();	return ret;}
bool chk(int tans) {
    init();	for (int i = 1; i <= n; i++) addedge(i+2*m, t, tans);
    for (int i = 1; i <= m; i++) addedge(s, i, tans), addedge(i, i+m, k);
    for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) addedge(G[i][j] ? i : i+m, j+2*m, 1);
    return Dinic() == n*tans;
}
int bi_search(int l, int r) {
    int ret = 0;
    while (l <= r)
        if (!chk(mid)) r = mid-1;
        else ret = mid, l = mid+1;
    return ret;
}
int main() {
    int T;	read(T);
    for (int C = 1; C <= T; C++) {
        read(n), read(m), read(f), read(k), memset(G, false, sizeof G);
        for (int i = 0, x, y; i < f; i++) read(x), read(y), G[y][x] = true;
        printf("Case %d: %d\n", C, bi_search(1, m));
    }
    return 0;
}