QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#209406 | #6319. Parallel Processing (Easy) | ucup-team870 | WA | 1ms | 4352kb | C++14 | 4.2kb | 2023-10-10 14:53:38 | 2023-10-10 14:53:39 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N = 20010;
struct Edge {
int to, next, flow;
} ed[N], tmp[N];
int head[N], sz = -1, cur[N], deep[N], s, t, vis[N], ksj[N];
vector<int> e[N];
void addEdge(int from, int to, int flow) {
sz++;
ed[sz].next = head[from];
head[from] = sz;
ed[sz].flow = flow;
ed[sz].to = to;
}
void add(int u, int v, int flow) {
addEdge(u, v, flow);
addEdge(v, u, 0);
}
bool bfs() {
queue <int> q;
q.push(s);
memset(deep, 0, sizeof(deep));
deep[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i != -1; i = ed[i].next) {
int v = ed[i].to;
if (deep[v] == 0 && ed[i].flow > 0) {
deep[v] = deep[u] + 1;
q.push(v);
if (v == t) return true;
}
}
}
return false;
}
int dfs(int u, int flow) {
if (u == t) return flow;
int rest = flow;
for (int i = cur[u]; i != -1; i = ed[i].next) {
int v = ed[i].to;
if (deep[v] == deep[u] + 1 && ed[i].flow > 0 && rest) {
int now = dfs(v, min(ed[i].flow, rest));
if (!now) deep[v] = 0;
rest -= now;
ed[i].flow -= now;
ed[i^1].flow += now;
if (ed[i].flow) cur[u] = i;
if (rest == 0) break;
}
}
if (rest == flow) deep[u] = -1;
return flow - rest;
}
int dinic() {
int flow = 0;
while (bfs()) {
for (int i = 1; i <= t; i++) cur[i] = head[i];
flow += dfs(s, 1e9);
}
return flow;
}
stack<int> stt;
int low[N], dfn[N], inst[N], cnt, bel[N], num;
void tarjan(int u) {
dfn[u] = low[u] = ++cnt;
stt.push(u), inst[u] = 1;
for (auto v: e[u]) {
if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if (inst[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
int now;
num++;
do {
now = stt.top();
stt.pop();
inst[now] = 0;
bel[now] = num;
} while (now != u);
}
}
int fa[N];
bool solve(int u, int kk) {
vis[u] = 1;
// cout <<u<<"$"<<endl;
for (int i = head[u]; i!=-1; i = ed[i].next) {
int v = ed[i].to;
if (vis[v]) continue;
if (ed[i^1].flow == 0) continue;
// cout<<"#";
ed[i^1].flow--;
// cout << v<<' '<<t<<"$"<<endl;
if (v == t) {
fa[kk] = u-num;
// cout <<"#";
return true;
}
if (solve(v, kk)) return true;
ed[i^1].flow++;
}
return false;
}
int find(int x) {
return x == fa[x]? x: find(fa[x]);
}
int main() {
memset(head, -1, sizeof(head));
int n, m;
scanf("%d%d", &n, &m);
rep (i, 1, m) {
int u, v; scanf("%d%d", &u, &v);
tmp[i].to = u;
tmp[i].next = v;
e[u].push_back(v);
// e[v].push_back(u);
}
rep (i, 1, n) {
if (!dfn[i]) tarjan(i);
}
s = 2*num + 1, t = s+1;
rep (i, 1, t) fa[i] =i;
// cout<<m
rep (i, 1, m) {
int u = tmp[i].to, v = tmp[i].next;
if (bel[u] != bel[v]) {
// cout <<bel[u]<<' '<<bel[v]<<"#"<<endl;
add(bel[u], bel[v]+num, 1e9);
add(bel[u]+num, bel[v]+num, 1e9);
}
}
rep (i, 1, num) {
add(s, i, 1);
add(i+num, t, 1);
}
// cout << num - dinic()<<endl;
dinic();
int kk = 0;
for (int i = head[s]; i != -1; i = ed[i].next) {
if (ed[i].flow == 1) ksj[ed[i].to] = ++kk;//, cout << ed[i].to<<"%\n";
}
// cout <<kk<<endl;
for (int i = head[s]; i != -1; i = ed[i].next) {
if (ed[i].flow == 0) memset(vis, 0, sizeof(vis)), solve(ed[i].to, ed[i].to);
}
rep (i, 1, n) {
cout << ksj[find(bel[i])]<<' ';
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4352kb
input:
2
output:
2 1
result:
wrong answer L = 2 is larger than 1