QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #642031 | #5114. Cells Coloring | PonyHex | Compile Error | / | / | C++20 | 5.6kb | 2024-10-15 09:03:48 | 2024-10-15 09:03:49 |
Judging History
answer
PonyHex
登出
QOJ.ac
QOJ
ID 题目 提交者 结果 用时 内存 语言 文件大小 提交时间 测评时间
#642026 #5114. Cells Coloring PonyHex WA 568ms 14108kb C++20 5.1kb 2024 - 10 - 15 09:00 : 33 2024 - 10 - 15 09 : 00 : 34
Judging History
你现在查看的是最新测评结果
[2024 - 10 - 15 09:00 : 34]评测
测评结果：WA用时：568ms内存：14108kb
查看
[2024 - 10 - 15 09:00 : 33]提交
answer
#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define double long double
//#define int long long
#define lc u<<1
#define rc u<<1|1
#define endl "\n"
#define X first
#define Y second
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> PII;
const ll N = 2e5 + 50;
const ll maxm = 2e18;
const ll mod = 1e9 + 7;
ll exgcd(ll a, ll b, ll& x, ll& y);
ll ksm(ll a, ll b) {
ll base = a;
ll ans = 1;
while (b) {
if (b & 1)ans *= base;
ans %= mod;
base *= base; base %= mod;
b >>= 1;
}
return ans % mod;
}
char mp[300][300];
ll n, m, cc, dd;
//ll mf[N * 2], prv[N * 2];
ll cur[N * 2], d[N * 2];
ll st, ed;
struct eage {
ll v, next, c;
}e[N];
ll h[N], idx = 1;
void add(ll u, ll v, ll c) {
e[++idx] = { v,h[u],c }; h[u] = idx;
e[++idx] = { u,h[v],c }; h[v] = idx;
}
bool bfs() {//在残量网络中构建分层图
//memset(d, 0, sizeof(d));
for (int i = 1; i <= n + m + 2; i++)d[i] = 0;
queue<ll>q;
q.push(st);
d[st] = 1;
while (q.size()) {//我们对此时能达到的节点构造分层图
ll u = q.front(); q.pop();
for (int i = h[u]; i; i = e[i].next) {
ll v = e[i].v;
if (d[v] == 0 && e[i].c) {//变化的残量网络中，一部分容量已经无了，所以我们直接把他从分层图中踢出去
d[v] = d[u] + 1;
q.push(v);
if (v == ed)return true;
}
}
}
//不存在prv数组不需要记录入边编号，没有mf数组，不需要在bfs的时候顺路记录mflow
return false;
}
ll dfs(ll u, ll mf) {//判断我们在分层图中所处的位置，记录当前路径的最大流
if (u == ed)return mf;
//走到汇点了，我们能得到流
ll sum = 0;//记录当前节点后能获取多大的流，然后返回
for (int i = cur[u]; i; i = e[i].next) {//遍历能到达的所有节点
cur[u] = i;//当前弧优化，就是说走到过的最远的弧，我们下次要是再走，就从这个弧开始
ll v = e[i].v;
if (e[i].c && d[v] == d[u] + 1) {
ll mid = dfs(v, min(mf, e[i].c));
sum += mid;
e[i].c -= mid;
e[i ^ 1].c += mid;
mf -= mid;//我就说忘了什么
if (mf == 0)break;
/*
if (e[i].c == 0)d[i] = 0;
*/
}
}
//很多细节都没记住，
//包括这个
if (sum == 0)d[u] = 0;//从图中踢出去
//在上面我写了一个，残量为0的时候从图中踢出去
//但是显然sum为0更合理因为残量不为0如果后续残量为0我们依然无法获取新的路径
//所以我们根据sum为0来判断是否移除出图
return sum;
}
ll dinic() {
ll flow = 0;
while (bfs()) {//判断是否能够开拓出增广路径，并且构建出分层图
memcpy(cur, h, sizeof h);
flow += dfs(st, maxm);
}
return flow;
}
void solve()
{
//现在尝试网络流解法,听xixu说起，其实是要对行和列建边，
//其实有思路，但是不知道是不是正解
cin >> n >> m >> cc >> dd; idx = 0;
st = n + m + 1; ed = n + m + 2;
ll mx = 0, sum = 0;
for (int i = 1; i <= n; i++) {
ll mid = 0;
for (int j = 1; j <= m; j++) {
cin >> mp[i][j];
if (mp[i][j] == '.')mid++, sum++;
}
mx = max(mx, mid);
}
for (int j = 1; j <= m; j++) {
ll mid = 0;
for (int i = 1; i <= n; i++) {
if (mp[i][j] == '.')mid++;
}
mx = max(mx, mid);
}
ll ans = maxm;
for (int c = 0; c <= mx; c++) {//枚举c建图，然后找最大流
for (int i = 1; i <= n + m + 2; i++)h[i] = 0;
idx = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
//对每行每列建边
if (mp[i][j] == '.') {
add(i, n + j, 1); add(n + j, i, 0);
}
}
}
for (int i = 1; i <= n; i++) {
add(st, i, c); add(i, st, 0);
}
for (int j = 1; j <= m; j++) {
add(n + j, ed, c); add(ed, n + j, 0);
}
ll val = dinic(); //cout << val << endl;
ans = min(ans, cc * c + dd * (sum - val));
}
cout << ans << endl;
return;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
ll t = 1; //cin >> t;
while (t--)solve();
return 0;
}
/*PonyHex*/
ll exgcd(ll a, ll b, ll& x, ll& y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
ll g = exgcd(b, a % b, x, y);
ll temp = x;
x = y;
y = temp - (a / b) * y;
return g;
}
/*
1
11
1 2 3 2 5 6 7 6 9 1
*/
/*
ll ksm(ll a, ll b) {
ll base = a;
ll ans = 1;
while (b) {
if (b & 1)ans *= base;
base *= base;
b >>= 1;
}
return ans;
}*/
/*
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}*/
详细
answer.code:7:9: error: "#" is not a valid filename
7 | #642026 #5114. Cells Coloring PonyHex WA 568ms 14108kb C++20 5.1kb 2024 - 10 - 15 09:00 : 33 2024 - 10 - 15 09 : 00 : 34
| ^
answer.code:11:17: error: invalid digit "9" in octal constant
11 | [2024 - 10 - 15 09:00 : 34]评测
| ^~
answer.code:14:17: error: invalid digit "9" in octal constant
14 | [2024 - 10 - 15 09:00 : 33]提交
| ^~
answer.code:1:1: error: ‘PonyHex’ does not name a type
1 | PonyHex
| ^~~~~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:62,
from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from answer.code:17:
/usr/include/c++/13/ext/type_traits.h:164:35: error: ‘constexpr const bool __gnu_cxx::__is_null_pointer’ redeclared as different kind of entity
164 | __is_null_pointer(std::nullptr_t)
| ^
/usr/include/c++/13/ext/type_traits.h:159:5: note: previous declaration ‘template<class _Type> constexpr bool __gnu_cxx::__is_null_pointer(_Type)’
159 | __is_null_pointer(_Type)
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/13/ext/type_traits.h:164:26: error: ‘nullptr_t’ is not a member of ‘std’; did you mean ‘nullptr_t’?
164 | __is_null_pointer(std::nullptr_t)
| ^~~~~~~~~
In file included from /usr/include/c++/13/cstddef:50,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:41:
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:443:29: note: ‘nullptr_t’ declared here
443 | typedef decltype(nullptr) nullptr_t;
| ^~~~~~~~~
In file included from /usr/include/c++/13/bits/stl_pair.h:60,
from /usr/include/c++/13/bits/stl_algobase.h:64:
/usr/include/c++/13/type_traits:510:26: error: ‘std::size_t’ has not been declared
510 | template<typename _Tp, std::size_t _Size>
| ^~~
/usr/include/c++/13/type_traits:511:25: error: ‘_Size’ was not declared in this scope
511 | struct is_array<_Tp[_Size]>
| ^~~~~
/usr/include/c++/13/type_traits:511:31: error: template argument 1 is invalid
511 | struct is_array<_Tp[_Size]>
| ^
/usr/include/c++/13/type_traits:617:33: error: ‘nullptr_t’ is not a member of ‘std’; did you mean ‘nullptr_t’?
617 | struct is_null_pointer<std::nullptr_t>
| ^~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:443:29: note: ‘nullptr_t’ declared here
443 | typedef decltype(nullptr) nullptr_t;
| ^~~~~~~~~
/usr/include/c++/13/type_traits:617:42: error: template argument 1 is invalid
617 | struct is_null_pointer<std::nullptr_t>
| ^
/usr/include/c++/13/type_traits:621:48: error: template argument 1 is invalid
621 | struct is_null_pointer<const std::nullptr_t>
| ^
/usr/include/c++/13/type_traits:625:51: error: template argument 1 is invalid
625 | struct is_null_pointer<volatile std::nullptr_t>
| ^
/usr/include/c++/13/type_traits:629:57: error: template argument 1 is invalid
629 | struct is_null_pointer<const volatile std::nullptr_t>
| ^
/usr/include/c++/13/type_traits:1348:37: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
1348 | : public integral_constant<std::size_t, alignof(_Tp)>
| ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
214 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
/usr/include/c++/13/type_traits:1348:57: error: template argument 1 is invalid
1348 | : public integral_constant<std::size_t, alignof(_Tp)>
| ^
/usr/include/c++/13/type_traits:1357:37: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
1357 | : public integral_constant<std::size_t, 0> { };
| ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
214 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
/usr/include/c++/13/type_traits:1357:46: error: template argument 1 is invalid
1357 | : public integral_constant<std::size_t, 0> { };
| ^
/usr/include/c++/13/type_traits:1359:26: error: ‘std::size_t’ has not been declared
1359 | template<typename _Tp, std::size_t _Size>
| ^~~
/usr/include/c++/13/type_traits:1360:21: error: ‘_Size’ was not declared in this scope
1360 | st...