QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#103049 | #6329. Colorful Graph | Alpha_Q# | RE | 2ms | 4228kb | C++17 | 2.2kb | 2023-05-04 06:16:50 | 2023-05-04 06:16:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 7002;
const int INF = 1e8 + 5;
bitset <N> adj[N];
int m, match[N << 1], dist[N << 1];
bool bfs() {
queue <int> q;
for (int i = 1; i <= m + m; ++i) {
if (!match[i]) dist[i] = 0, q.emplace(i);
else dist[i] = INF;
}
dist[0] = INF;
while (!q.empty()) {
int u = q.front(); q.pop();
if (!u) continue;
for (int v = m + 1; v <= m + m; ++v) if (adj[u][v - m]) {
if (dist[match[v]] == INF) {
dist[match[v]] = dist[u] + 1,
q.emplace(match[v]);
}
}
}
return dist[0] != INF;
}
bool dfs (int u) {
if (!u) return 1;
for (int v = m + 1; v <= m + m; ++v) if (adj[u][v - m]) {
if (dist[match[v]] == dist[u] + 1 and dfs(match[v])) {
match[u] = v, match[v] = u;
return 1;
}
}
dist[u] = INF;
return 0;
}
int hopcroftKarp() {
int ret = 0;
while (bfs()) {
for (int i = 1; i <= m; ++i) {
ret += !match[i] and dfs(i);
}
}
return ret;
}
bool vis[N];
int n, comp[N], root, in[N], ans[N];
vector <int> stk, g[N], h[N], dag[N];
void forw (int u) {
vis[u] = 1;
for (int v : g[u]) if (!vis[v]) forw(v);
stk.emplace_back(u);
}
void bacw (int u) {
comp[u] = m;
for (int v : h[u]) if (!comp[v]) bacw(v);
}
void mark (int u) {
adj[root][u] = 1;
for (int v : dag[u]) if (!adj[root][v]) mark(v);
}
int main() {
cin >> n >> m;
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
g[u].emplace_back(v);
h[v].emplace_back(u);
}
for (int i = 1; i <= n; ++i) if (!vis[i]) forw(i);
reverse(stk.begin(), stk.end()), m = 0;
for (int i : stk) if (!comp[i]) ++m, bacw(i);
for (int i = 1; i <= n; ++i) for (int j : g[i]) {
if (comp[i] ^ comp[j]) dag[comp[i]].emplace_back(comp[j]);
}
for (int i = 1; i <= m; ++i) root = i, mark(i), adj[i][i] = 0;
hopcroftKarp();
for (int i = 1; i <= m; ++i) if (match[i]) match[i] -= m, ++in[match[i]];
int color = 0;
for (int i = 1; i <= m; ++i) if (!in[i]) {
int at = i; ++color;
while (at) ans[at] = color, at = match[at];
}
for (int i = 1; i <= n; ++i) printf("%d ", ans[comp[i]]);
cout << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 4228kb
input:
5 5 1 4 2 3 1 3 2 5 5 1
output:
1 1 1 2 1
result:
ok AC
Test #2:
score: 0
Accepted
time: 1ms
memory: 4204kb
input:
5 7 1 2 2 1 4 3 5 1 5 4 4 1 4 5
output:
2 2 1 1 1
result:
ok AC
Test #3:
score: 0
Accepted
time: 2ms
memory: 4172kb
input:
8 6 6 1 3 4 3 6 2 3 4 1 6 4
output:
4 4 4 4 3 4 2 1
result:
ok AC
Test #4:
score: -100
Runtime Error
input:
7000 6999 4365 4296 2980 3141 6820 4995 4781 24 2416 5844 2940 2675 3293 2163 3853 5356 262 6706 1985 1497 5241 3803 353 1624 5838 4708 5452 3019 2029 6161 3849 4219 1095 1453 4268 4567 1184 1857 2911 3977 1662 2751 6353 6496 2002 6628 1407 4623 425 1331 4445 4277 1259 3165 4994 1044 2756 5788 5496 ...