「模拟赛」Yl

Description

若一个长度为 nn 的序列中 1n1\cdots n 各出现了恰好一次,我们称之为排列。
现在维尼想知道,是否可以构造一个长度为 nn 的排列,满足 mm 个限制,对于每个限制有 33 个权值 llrrqq,你需要使区间[l,r][l,r]的最大值为 qq
如果存在输出 Possible ,否则输出 Impossible

Input

本题有多组测试数据,第一行一个整数 TT,表示测试数据组数。
之后有 TT 组结构相同的数据:
每组数据的第一行有两个整数 nnmm
之后会有 MM 行,每行表示一个三元组 Li,Ri,QiL_i,R_i,Q_i
保证 1LiRin,1Qin1\leq Li\leq R_i\leq n,1\leq Q_i\leq n

Output

每组数据输出一行,即PossibleImpossible,输出不含引号。

Sample Input

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

Sample Output

1
2
Possible
Impossible

HINT

Solution

建立两类点,一类是权值为x1xnx_1\to x_n,一类为位置y1yny_1\to y_n
连边(S,xi,1),(Yi,T,1)(S, x_i,1),(Y_i,T,1)
枚举每一个权值,然后找到所有区间权值最大值是它的区间,取他们的交集理解[L,R][L,R],这个区间比如有这个权值,连边(xi,yj,1),j[L,R](x_i,y_j,1),j\in [L,R]
否则,连边(xi,yj,1),j[1,n],mxji(x_i,y_j,1),j\in [1,n],mx_j \ge i
SSTT跑一遍dinicdinic,判断是否最大流为nn就行了。

force

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
void setIO() {
freopen("yl.in","r",stdin);
freopen("yl.out","w",stdout);
}
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) x = -x, putchar('-');if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 2100, M = 1111011;
int n, m;
struct T {
int l, r, v;
}a[N];
int s, t;
struct Edge {
int u, v, nxt, f;
}e[M * 2];
int head[N], en, mx[N];
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = z;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
const int inf = 1e9;
int d[N];
bool bfs() {
queue<int>q;
q.push(s);
for(int i = 1; i <= t; ++i) d[i] = 0;
d[s] = 1;
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f) {
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int k, rest = flow;
for(int i = head[x]; i && rest; i = e[i].nxt) if(d[e[i].v] == d[x] + 1) {
int y = e[i].v;
k = dinic(y, min(e[i].f, rest));
e[i ^ 1].f += k;
e[i].f -= k;
rest -= k;
}
return flow - rest;
}
int h[N], H;
int main() {
setIO();
int T = read();
while(T--) {
n = read(), m = read();
en = 1;
H = 0;
if(n > 100) return 0;
memset(head, 0, sizeof head);
for(int i = 1; i <= n; ++i) mx[i] = inf;
for(int i = 1; i <= m; ++i) {
a[i].l = read(), a[i].r = read(), a[i].v = read();
h[++H] = a[i].v;
for(int j = a[i].l;j <= a[i].r; ++j) mx[j] = min(mx[j], a[i].v);
}
h[++H] = n;
sort(h + 1, h + 1 + H);
H = unique(h + 1, h + 1 + H) - h - 1;
s = n + 2 * H + 1;
t = n + 2 * H + 2;
for(int i = 1; i <= H; ++i) {
addedge(s, i, 1);
addedge(s, i + H, h[i] - h[i - 1] - 1);
}
for(int i = 1; i <= n; ++i)
addedge(i + H * 2, t, 1);
for(int i = 1; i <= H; ++i) {
int L = 0, R = inf;
for(int j = 1; j <= m; ++j)
if(a[j].v == h[i]) {
L = max(L, a[j].l);
R = min(R, a[j].r);
}
if(h[i] - h[i - 1] - 1)for(int j = 1; j <= n; ++j) if(mx[j] >= h[i]) addedge(i + H, j + H * 2, inf);
if(L){for(int j = L; j <= R; ++j) if(mx[j] >= h[i])addedge(i, j + H * 2, 1);} //if的问题
else for(int j = 1; j <= n; ++j) if(mx[j] >= h[i])addedge(i, j + H * 2, 1);
}
int res = 0, y;
while(bfs()) while(y = dinic(s, inf)) res += y;
if(res == n) puts("Possible");
else puts("Impossible");
}
return 0;
}

std

最后部分直接离散化就行了。

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
void setIO() {
freopen("yl.in","r",stdin);
freopen("yl.out","w",stdout);
}
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) x = -x, putchar('-');if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 3100000, M = 6110110;
int n, m;
struct T {
int l, r, v;
}a[N];
int s, t;
struct Edge {
int u, v, nxt, f;
}e[M * 2];
int head[N], en, mx[N];
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = z;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
const int inf = 1e9;
int d[N];
bool bfs() {
queue<int>q;
q.push(s);
for(int i = 1; i <= t; ++i) d[i] = 0;
d[s] = 1;
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f) {
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int k, rest = flow;
for(int i = head[x]; i && rest; i = e[i].nxt) if(d[e[i].v] == d[x] + 1) {
int y = e[i].v;
k = dinic(y, min(e[i].f, rest));
e[i ^ 1].f += k;
e[i].f -= k;
rest -= k;
}
return flow - rest;
}
int h[N], H;
int q[N], Q;
int main() {
setIO();
int T = read();
while(T--) {
n = read(), m = read();
en = 1;
Q = H = 0;
for(int i = 1; i <= m; ++i) {
a[i].l = read(), a[i].r = read(), a[i].v = read();
h[++H] = a[i].v;
if(a[i].l>1)q[++Q] = a[i].l - 1;
q[++Q] = a[i].r;
q[++Q] = a[i].l; //(l-1,l]形成
for(int j = a[i].l;j <= a[i].r; ++j) mx[j] = min(mx[j], a[i].v);
}
h[++H] = n;
q[++Q] = n;
sort(h + 1, h + 1 + H);
H = unique(h + 1, h + 1 + H) - h - 1;
sort(q + 1, q +1 + Q);
Q = unique(q + 1, q +1 +Q) - q - 1;
for(int i = 1; i <= Q; ++i) mx[i] = inf;
for(int i = 1; i <= m; ++i) {
a[i].l = lower_bound(q + 1, q + 1 + Q, a[i].l) - q;
a[i].r = lower_bound(q + 1, q + 1 + Q, a[i].r) - q;
for(int j = a[i].l;j <= a[i].r; ++j) mx[j] = min(mx[j], a[i].v);
}
for(int i = 1; i <= t; ++i) head[i] = 0;
s = Q + 2 * H + 1;
t = Q + 2 * H + 2;
for(int i = 1; i <= H; ++i) {
addedge(s, i, 1);
addedge(s, i + H, h[i] - h[i - 1] - 1);
}
for(int i = 1; i <= Q; ++i)
addedge(i + H * 2, t, q[i] - q[i - 1]);
for(int i = 1; i <= H; ++i) {
int L = 0, R = inf;
for(int j = 1; j <= m; ++j)
if(a[j].v == h[i]) {
L = max(L, a[j].l);
R = min(R, a[j].r);
}
if(h[i] - h[i - 1] - 1)for(int j = 1; j <= Q; ++j) if(mx[j] >= h[i]) addedge(i + H, j + H * 2, inf);
if(L){for(int j = L; j <= R; ++j) if(mx[j] >= h[i])addedge(i, j + H * 2, inf);} //if的问题
else for(int j = 1; j <= Q; ++j) if(mx[j] >= h[i])addedge(i, j + H * 2, inf);
}
int res = 0, y;
while(bfs()) while(y = dinic(s, inf)) res += y;
if(res == n) puts("Possible");
else puts("Impossible");
}
return 0;
}