ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#160 | #1. 第二个 A + B Problem | NagoriYuuuki | 97 | 36ms | 4644kb | C++23 | 2.8kb | 2025-04-17 14:12:29 | 2025-04-19 16:15:12 |
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define xx first
#define yy second
template <typename FlowType>
class NetFlow
{
private:
struct Edge
{
int to, next;
FlowType flow;
};
vector<Edge> edge;
vector<int> head;
vector<int> dep;
vector<int> now;
int tot = 1;
int n;
bool bfs()
{
fill(dep.begin(), dep.end(), 0);
queue<int> que;
que.push(s);
dep[s] = 1;
now[s] = head[s];
while (!que.empty())
{
int u = que.front();
que.pop();
for (int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].flow > 0 && dep[v] == 0)
{
que.push(v);
now[v] = head[v];
dep[v] = dep[u] + 1;
if (v == t)
return true;
}
}
}
return false;
}
FlowType dfs(int u, FlowType sum)
{
if (u == t)
return sum;
FlowType res = 0;
for (int &i = now[u]; i && sum > 0; i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].flow > 0 && dep[v] == dep[u] + 1)
{
FlowType k = dfs(v, min(sum, edge[i].flow));
if (k == 0)
dep[v] = 0;
edge[i].flow -= k;
edge[i ^ 1].flow += k;
res += k;
sum -= k;
}
}
return res;
}
public:
int s, t;
NetFlow(int n, int e, int s, int t)
{
this->n = n;
edge.resize(2 * e + 5);
head.resize(n + 5, 0);
dep.resize(n + 5, 0);
now.resize(n + 5, 0);
this->s = s;
this->t = t;
tot = 1;
}
void add(int u, int v, FlowType flow)
{
edge[++tot] = {v, head[u], flow};
head[u] = tot;
edge[++tot] = {u, head[v], 0};
head[v] = tot;
}
FlowType MaxFlow()
{
FlowType res = 0;
while (bfs())
res += dfs(s, numeric_limits<FlowType>::max());
return res;
}
};
signed main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int x, y;
cin >> x >> y;
const int offset = 1e4 + 10;
x += offset;
y += offset;
int n = x + y;
int s = 0, t = n + 1;
NetFlow<int> flow(t, 2 * n, s, t);
for (int i = 1; i <= n; i++)
{
flow.add(s, i, 1);
flow.add(i, t, 1);
}
int maxflow = flow.MaxFlow();
cout << maxflow - (offset << 1) << endl;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 6ms
memory: 4276kb
input:
23 24
output:
47
result:
ok 1 number(s): "47"
Test #2:
score: 10
Accepted
time: 3ms
memory: 4376kb
input:
233 1
output:
234
result:
ok 1 number(s): "234"
Test #3:
score: 10
Accepted
time: 6ms
memory: 4448kb
input:
222 333
output:
555
result:
ok 1 number(s): "555"
Test #4:
score: 10
Accepted
time: 6ms
memory: 4336kb
input:
1 333
output:
334
result:
ok 1 number(s): "334"
Test #5:
score: 10
Accepted
time: 0ms
memory: 4276kb
input:
222 333
output:
555
result:
ok 1 number(s): "555"
Test #6:
score: 10
Accepted
time: 3ms
memory: 4416kb
input:
242 333
output:
575
result:
ok 1 number(s): "575"
Test #7:
score: 10
Accepted
time: 5ms
memory: 4540kb
input:
222 3330
output:
3552
result:
ok 1 number(s): "3552"
Test #8:
score: 10
Accepted
time: 4ms
memory: 4632kb
input:
2220 333
output:
2553
result:
ok 1 number(s): "2553"
Test #9:
score: 10
Accepted
time: 2ms
memory: 4476kb
input:
222 555
output:
777
result:
ok 1 number(s): "777"
Test #10:
score: 10
Accepted
time: 1ms
memory: 4644kb
input:
222 3333
output:
3555
result:
ok 1 number(s): "3555"
Extra Test:
score: -3
Extra Test Failed : Dangerous Syscalls on 2
input:
100000000 100000000