用户输出
2
系统信息
Exited with return code 0| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #47979 | #1257. 车 | Accepted | 100 | 174 ms | 4340 K | C++ 11 (Clang) / 3.4 K | Rhodoks | 2021-05-10 11:41:10 |
#include <bits/stdc++.h>
#define DB double
#define LL long long
#define MST(a, b) memset((a), (b), sizeof(a))
#ifdef _DEBUG_
#define MRK() cout << "Mark" << endl;
#define WRT(x) cout << #x << " = " << (x) << endl;
#else
#define MRK() ;
#define WRT(x) ;
#endif
#define MAXN 1010000
#define MAXM 2010000
#define MOD 998244353 // 1000000007
#define LLINF 0x3f3f3f3f3f3f3f3f
#define EPS 1e-5
#define _ 0
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m, s, t;
int maxflow = 0;
struct EDGE {
int to, weight, next;
} edge[MAXM << 1];
int head[MAXN];
int deep[MAXN];
int cnt = 0;
inline void add(int x, int y, int w) {
edge[cnt].to = y;
edge[cnt].weight = w;
edge[cnt].next = head[x];
head[x] = cnt++;
edge[cnt].to = x;
edge[cnt].weight = 0;
edge[cnt].next = head[y];
head[y] = cnt++;
}
bool bfs() {
int cur;
queue<int> q;
for (int i = 1; i <= n; i++) deep[i] = -1;
deep[s] = 0;
q.push(s);
while (!q.empty()) {
cur = q.front();
q.pop();
for (int i = head[cur]; ~i; i = edge[i].next)
if (!~deep[edge[i].to] && edge[i].weight) {
deep[edge[i].to] = deep[cur] + 1;
q.push(edge[i].to);
}
}
if (~deep[t])
return true;
else
return false;
}
int dfs(int cur, int limit) {
if (!limit || cur == t)
return limit;
int flow = 0;
int f;
for (int i = head[cur]; ~i; i = edge[i].next) {
if (deep[edge[i].to] == deep[cur] + 1 && (f = dfs(edge[i].to, min(limit, edge[i].weight)))) {
flow += f;
limit -= f;
edge[i].weight -= f;
edge[i ^ 1].weight += f;
if (!limit)
break;
}
}
if (!flow)
deep[cur] = -1;
return flow;
}
int dinic() {
maxflow = 0;
while (bfs()) maxflow += dfs(s, INF);
return maxflow;
}
int chess[1010][1010];
/* 模板开始 */
// Union_Find_Set 并查集
// union_find_set(int set_size=MAXN) 传入变量为变长数组长度
// void init(int n) 初始化
// void merge(int x,int y) 合并两个集合
// bool query(int x,int y) 查询两个元素是否在一个集合
class Union_Find_Set {
int *pa;
int n;
public:
int Getpa(int x) { return pa[x] == x ? x : (pa[x] = Getpa(pa[x])); }
int operator[](int x) { return Getpa(x); }
Union_Find_Set(int _size = MAXN) {
n = _size;
pa = new int[_size + 2];
Init(_size);
}
~Union_Find_Set() { delete pa; }
void Init(int n) {
for (int i = 0; i <= n; i++) pa[i] = i;
}
void Merge(int x, int y) { pa[Getpa(x)] = Getpa(y); }
bool Query(int x, int y) { return Getpa(x) == Getpa(y); }
int Size() { return n; }
};
typedef Union_Find_Set UFS;
/* 模板结束 */
int visit[MAXN];
void input() {
int x, y, w;
cin >> n >> m;
s = 2 * n + 1;
t = 2 * n + 2;
for (int i = 1; i <= t; i++) head[i] = -1;
for (int i = 1; i <= n; i++) add(s, i, 1);
for (int i = n + 1; i <= 2 * n; i++) add(i, t, 1);
for (int i = 0; i < m; i++) {
scanf("%d%d", &x, &y);
chess[x][y] = 1;
visit[y]++;
add(x, y + n, 1);
}
UFS ufs(n + 1);
ufs.Init(n + 1);
int ans = 0;
for (int i = 1; i <= n; i++) {
int lst = -1;
for (int j = 1; j <= n; j++)
if (chess[i][j] == 1) {
if (lst > 0)
ufs.Merge(lst, j);
lst = j;
}
}
for (int i = 1; i <= n; i++)
if (visit[ufs.Getpa(i)] > 0)
visit[ufs.Getpa(i)] = -1;
for (int i = 1; i <= n; i++)
if (visit[i] < 0)
ans++;
n = t;
cout << m - ans << endl;
}
int main() {
#ifdef _DEBUG_
freopen("C:/Users/DELL/Documents/Dev-C++/sample.in", "r", stdin);
#endif
input();
return ~~(0 ^ _ ^ 0);
}用户输出
8
系统信息
Exited with return code 0用户输出
9
系统信息
Exited with return code 0用户输出
12
系统信息
Exited with return code 0用户输出
12
系统信息
Exited with return code 0用户输出
17
系统信息
Exited with return code 0用户输出
17
系统信息
Exited with return code 0用户输出
16
系统信息
Exited with return code 0用户输出
14
系统信息
Exited with return code 0901 598
565 361
500 175
205 860
524 404
193 20
190 212
379 254
654 653
174 763
344 42
271 140
76 774
<4567 bytes omitted>用户输出
330
系统信息
Exited with return code 0530 551
370 236
26 367
405 200
55 355
436 316
478 344
397 315
476 392
60 512
233 526
514 248
429 325
<4086 bytes omitted>用户输出
396
系统信息
Exited with return code 0904 84
121 471
711 121
862 151
441 193
514 539
479 427
342 129
583 269
260 175
607 462
641 578
282 2
<560 bytes omitted>用户输出
2
系统信息
Exited with return code 0322 197
178 243
39 189
83 306
293 89
254 60
223 82
96 176
262 302
276 15
135 248
265 232
63 281
179
<1356 bytes omitted>用户输出
91
系统信息
Exited with return code 0569 804
264 153
179 489
204 404
121 227
309 101
534 470
361 276
537 107
474 107
513 334
167 332
313
<6023 bytes omitted>用户输出
729
系统信息
Exited with return code 0254 526
54 106
142 201
49 219
238 117
136 242
171 196
132 49
59 44
195 169
103 230
222 77
154 159
14
<3680 bytes omitted>用户输出
511
系统信息
Exited with return code 0300 844
197 204
168 265
277 270
101 251
192 36
222 79
270 212
242 139
161 124
169 220
182 249
177 25
<6051 bytes omitted>用户输出
839
系统信息
Exited with return code 0503 668
81 343
481 83
182 390
22 300
487 210
278 503
164 337
90 1
437 244
219 20
98 97
210 262
76 42
<5008 bytes omitted>用户输出
577
系统信息
Exited with return code 0300 848
273 182
240 132
279 174
237 281
279 180
131 34
24 238
239 8
274 237
63 24
79 233
204 105
75
<6055 bytes omitted>用户输出
841
系统信息
Exited with return code 0166 728
126 14
151 109
118 126
112 37
76 151
6 71
98 94
117 79
101 90
84 42
117 112
42 7
54 6
155 98
<4795 bytes omitted>用户输出
727
系统信息
Exited with return code 07 49
1 1
1 2
1 3
1 4
1 5
1 6
1 7
2 1
2 2
2 3
2 4
2 5
2 6
2 7
3 1
3 2
3 3
3 4
3 5
3 6
3 7
4 1
4 2
4 3
<101 bytes omitted>用户输出
48
系统信息
Exited with return code 015 225
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
2 1
2 2
2 3
2 4
2 5
2 6
2 7
<987 bytes omitted>用户输出
224
系统信息
Exited with return code 026 676
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1
<3495 bytes omitted>用户输出
675
系统信息
Exited with return code 031 961
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1
<5115 bytes omitted>用户输出
960
系统信息
Exited with return code 0666 999
1 1
1 2
2 2
4 3
3 4
4 4
5 5
6 5
6 6
7 7
8 7
7 8
9 9
9 10
10 10
12 11
11 12
12 12
13 13
14 13
<7576 bytes omitted>用户输出
666
系统信息
Exited with return code 0666 999
2 1
1 2
2 2
4 3
3 4
4 4
5 5
6 5
6 6
8 7
7 8
8 8
9 9
10 9
9 10
12 11
11 12
12 12
13 13
14 13
<7576 bytes omitted>用户输出
666
系统信息
Exited with return code 0666 999
2 1
1 2
2 2
3 3
4 3
4 4
6 5
5 6
6 6
7 7
7 8
8 8
9 9
10 9
10 10
11 11
11 12
12 12
13 13
14 13
<7576 bytes omitted>用户输出
666
系统信息
Exited with return code 0666 999
2 1
1 2
2 2
3 3
4 3
3 4
5 5
6 5
5 6
8 7
7 8
8 8
9 9
10 9
10 10
11 11
11 12
12 12
13 13
14 13
<7575 bytes omitted>用户输出
666
系统信息
Exited with return code 0666 999
2 1
1 2
2 2
3 3
3 4
4 4
5 5
6 5
6 6
7 7
7 8
8 8
9 9
10 9
10 10
11 11
11 12
12 12
13 13
14 13
<7576 bytes omitted>用户输出
666
系统信息
Exited with return code 0666 999
1 1
1 2
2 2
3 3
4 3
4 4
5 5
5 6
6 6
7 7
8 7
8 8
9 9
10 9
9 10
11 11
11 12
12 12
14 13
13 14
<7575 bytes omitted>用户输出
666
系统信息
Exited with return code 0666 999
1 1
2 1
2 2
3 3
3 4
4 4
6 5
5 6
6 6
7 7
8 7
8 8
9 9
10 9
10 10
11 11
12 11
12 12
13 13
14 13
<7577 bytes omitted>用户输出
666
系统信息
Exited with return code 0666 999
1 1
2 1
1 2
3 3
4 3
3 4
5 5
5 6
6 6
7 7
7 8
8 8
9 9
10 9
10 10
11 11
12 11
11 12
13 13
13 14
<7575 bytes omitted>用户输出
666
系统信息
Exited with return code 0666 999
2 1
1 2
2 2
3 3
4 3
3 4
5 5
5 6
6 6
8 7
7 8
8 8
9 9
10 9
10 10
11 11
12 11
12 12
13 13
14 13
<7576 bytes omitted>用户输出
666
系统信息
Exited with return code 0666 999
2 1
1 2
2 2
3 3
4 3
3 4
5 5
6 5
5 6
7 7
8 7
7 8
9 9
10 9
9 10
12 11
11 12
12 12
13 13
13 14
<7575 bytes omitted>用户输出
666
系统信息
Exited with return code 0用户输出
9
系统信息
Exited with return code 0用户输出
9
系统信息
Exited with return code 0100 100
1 55
2 55
3 55
4 55
5 55
6 55
7 55
8 55
9 55
10 55
11 55
12 55
13 55
14 55
15 55
16 55
17 55
<500 bytes omitted>用户输出
99
系统信息
Exited with return code 0100 100
81 1
81 2
81 3
81 4
81 5
81 6
81 7
81 8
81 9
81 10
81 11
81 12
81 13
81 14
81 15
81 16
81 17
<500 bytes omitted>用户输出
99
系统信息
Exited with return code 01000 1000
1 608
2 608
3 608
4 608
5 608
6 608
7 608
8 608
9 608
10 608
11 608
12 608
13 608
14 608
1
<7803 bytes omitted>用户输出
999
系统信息
Exited with return code 0