Make the Team
filename: maketeam
Difficulty Level: Medium-Hard
Time Limit: 5 seconds
You are eager to make the programming team. You have decided that if you watch several videos, you will increase your chances of making the team. Each video you want to watch is one hour long, and each video plays at specific times. Naturally, you want to get through all the videos as fast as possible, to leave more time to practice! For example, if you want to watch two videos and the first one is available at the time intervals [1,2), [4,5), [8,9) and [12,13), and the second video is available at the time intervals [4,5), [7,8), and [11,12), then the earliest time at which you can complete the two videos is time 5. You can accomplish this by watching the first video in the time interval [1,2) and the second one at the time interval [4,5). Note that all videos play for precisely the length of one time interval, and one can watch back to back videos. Thus, if one video plays at the interval [x, x+1) and another video plays at the interval [x+1, x+2), where x is a positive integer, both can be watched, back to back.
The Problem:
Given a list of times that each video you want to watch is available, determine the earliest time at which you can complete watching all of the videos. Note that the videos can be watched in any order as long as the time intervals allow.
The first input line contains a single integer, n (1 ≤ n ≤ 200), indicating the number of videos you would like to watch. Each of the next n input lines describes a video you want to watch. The ith of these input lines starts with an integer, t_i (1 ≤ t_i ≤ 30), representing the number of times video i is available to watch. This is followed by t_i space separated values indicating the starting time video i is available to watch. The list of times for each video will be a strictly increasing list of positive integers, with a maximum value of 1000. It is guaranteed that there will be at least one arrangement that allows you to watch all of the videos.
The Output:
Print the earliest time at which you can complete watching all of the videos.
Solving
对可能的电影结束的时间节点与各个电影序号建立二分图，建立源点与汇点，源点连向各个电影节点，设定容量为1，各个电影节点连边连向所有的可能结束的时间节点，容量为1
我们提前将各可能结束的时间节点存入set中，升序排序，遍历过程中，将当前可能结束的时间节点连向汇点一条容量为1的边，代表可以有一个电影在此时播放，然后创建一个当前图的实例的拷贝（不能每次加边再跑最大流，因为这样是在上一次跑最大流后的图的残余网络上跑），跑一遍最大流，查看最大流流量是否等于电影节点数，若等于则代表此时所有的电影节点都已经被播放完毕，此时输出当前时间+1即可。
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3fLL
#define NINF -0x3f3f3f3f3f3f3f3fLL
#define Single
using namespace std;
typedef pair<int,int> pii;
// const int MOD = 998244353;
const int MOD = 1000000007;
const int N = 0;
template<class T>
struct Flow{
int n;
struct Edge {
int to, next; T cap;
};
vector<Edge> edge;
vector<int> cur;
vector<int> depth;
vector<int> head;
int eid;
Flow(int n,int m) {
init(n,m);
}
void init(int n,int m) {
this->n =n;
edge.resize(2 * m + 2);
depth.resize(n+ 1);
cur.resize(n+1);
head.assign(n+1,0);
eid = 1;
}
void addedge(int u,int v, T cap) {
edge[++eid] = {v,head[u],cap};
head[u] = eid;
edge[++eid] = {u,head[v],0};
head[v] = eid;
}
bool bfs(int s,int t) {
fill(depth.begin(),depth.end(),0);
queue<int> que;
depth[s] = 1;
que.push(s);
while(!que.empty()) {
const int u = que.front();
que.pop();
for(int i=head[u];i;i=edge[i].next) {
int v = edge[i].to;
T cap = edge[i].cap;
if(cap and depth[v] == 0) {
depth[v] = depth[u] + 1;
if(v == t) return true;
que.push(v);
}
}
}
return false;
}
T dfs(int u,int t, T mf) {
if(u == t) return mf;
T sum = 0;
for(int i=cur[u];i;i=edge[i].next) {
cur[u] = i;
int v = edge[i].to;
T cap = edge[i].cap;
if(depth[v] == depth[u] + 1 and cap) {
T f = dfs(v,t,min(mf,cap));
edge[i].cap -= f;
edge[i^1].cap += f;
sum += f;
mf -= f;
if(mf == 0) break;
}
}
if(sum == 0) depth[u] = 0;
return sum;
}
T maxflow(int s,int t) {
T ans = 0;
while(bfs(s,t)) {
for(int i=0;i<=n;i++) cur[i] = head[i];
ans += dfs(s,t,INF);
}
return ans;
}
};
void solve() {
Flow<int> mf(1e4+10,2e5);
int n;
cin >> n;
int t = 10001, s = 10002;
// 1 ~ 1000 time node
// 1001 ~ 1000 + n film node
for(int i=1001;i<=1000+n;i++) mf.addedge(s,i,1);
set<int> end;
for(int i=1;i<=n;i++){
int t;
cin >> t;
for(int j=1;j<=t;j++) {
int time;
cin >> time;
end.insert(time);
mf.addedge(i+1000,time,1);
}
}
for(auto x : end) {
mf.addedge(x,t,1);
auto mmf = mf;
// cout << mmf.maxflow(s,t) << endl;
if(mmf.maxflow(s,t) == n) {
cout << x + 1 << endl;
return;
}
}
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
#ifdef Single
T = 1;
#else
cin >> T;
#endif
while(T--) solve();
return 0;
}
|