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...