QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468604#6359. 游戏little_sun100 ✓2ms7716kbC++142.9kb2024-07-08 21:48:322024-07-08 21:48:33

Judging History

你现在查看的是最新测评结果

  • [2024-07-08 21:48:33]
  • 评测
  • 测评结果:100
  • 用时:2ms
  • 内存:7716kb
  • [2024-07-08 21:48:32]
  • 提交

answer

#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
#define meow(cat...) fprllf(stderr, cat)

const ll Max = 1e2 + 10;
const ll inf = 1e17;
const ll MaxN = 1e5 + 10;

struct edge
{
    ll next, to, flow;
} e[MaxN << 1];

char str[Max][Max];
ll row[Max][Max], col[Max][Max];
ll n, m, ans, s = 20001, t = 20002, cnt = 1;
ll now, head[MaxN], dep[MaxN], cur[MaxN];

void add(ll u, ll v, ll f)
{
    ++cnt;
    e[cnt].to = v;
    e[cnt].flow = f;
    e[cnt].next = head[u];
    head[u] = cnt;
} 

void add_edge(ll u, ll v, ll f) { add(u, v, f), add(v, u, 0); }

ll bfs()
{
    memset(dep, 0, sizeof(dep));
    memcpy(cur, head, sizeof(head));
    std::queue<ll> q; q.push(s), dep[s] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].to, c = e[i].flow;
            if(dep[v] || !c) continue;
            dep[v] = dep[u] + 1, q.push(v);
        }
    }
    return dep[t];
}

ll dinic(ll u, ll flow)
{
    if(u == t) return flow;
    ll rest = flow;
    for(int i = cur[u]; i && rest; i = e[i].next)
    {
        cur[u] = i; ll v = e[i].to, c = e[i].flow, k;
        if(dep[v] != dep[u] + 1 || !c) continue;
        k = dinic(v, std::min(rest, c));
        if(!k) dep[v] = -1;
        else e[i].flow -= k, e[i ^ 1].flow += k, rest -= k;
    }
    if(flow - rest < flow) dep[u] = -1;
    return flow - rest;
}

inline ll read()
{
    ll x = 0;
    char ch = getchar();
    while(ch > '9' || ch < '0')
        ch = getchar();
    while(ch <= '9' && ch >= '0') 
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}

void solve()
{
    ll now = 0;
    while(bfs())
        while((now = dinic(s, inf)))
            ans += now;
}

signed main()
{   
    n = read(), m = read();
    for(int i = 1; i <= n; i++)
        scanf("%s", str[i] + 1);
    for(int i = 1; i <= n; i++)
    {
        ++now, add_edge(s, now, 1);
        for(int j = 1; j <= m; j++)
        {
            if(str[i][j] == '#') 
                ++now, add_edge(s, now, 1);
            row[i][j] = now;
        }
    }
    for (int j = 1; j <= m; j++)
    {
        ++now, add_edge(now, t, 1);
        for (int i = 1; i <= n; i++)
        {
            if (str[i][j] == '#') 
                ++now, add_edge(now, t, 1);
            col[i][j] = now;
        }
    }
    // for(int i = 1; i <= n; i++)
    //     for(int j = 1; j <= m; j++)
    //         printf("%lld%c", row[i][j], " \n"[j == m]);
    // for (int i = 1; i <= n; i++)
    //     for (int j = 1; j <= m; j++)
    //         printf("%lld%c", col[i][j], " \n"[j == m]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(str[i][j] == '*')
                add_edge(row[i][j], col[i][j], 1);
    solve(), printf("%lld\n", ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 1ms
memory: 6988kb

input:

11 10
#*x#xx*x#*
*x*#*xx#*x
*#*xx*#***
x#x*x#*xx#
#x*x####*x
#x***###x#
x#####xxxx
#x###x##xx
#####xx##x
###x##xxx#
#xx######x

output:

12

result:

ok 1 number(s): "12"

Test #2:

score: 10
Accepted
time: 0ms
memory: 6472kb

input:

31 20
x#xx#*###x#*#*#*xx**
x#*x*##*###*x**#*x*#
###***###x*##x#x****
xx#x#x**#x#x#*xxx##*
*###xx**xx*x##x##xxx
##x#x#x##x#x#x##x###
x####x##x###xxx#####
###x####x#xx#x###x#x
##x###x###xx#xxxx###
#xx#x#x###xxx##x####
#x###xx##x######x###
#####x#######x##x##x
#######x#x###xx#####
x########x#####x####
...

output:

15

result:

ok 1 number(s): "15"

Test #3:

score: 10
Accepted
time: 1ms
memory: 6452kb

input:

31 20
*xx**#x**#x#**#***##
#*xx*####*##x*x#**##
#x*x*##*x#xx#xxxx###
*xx##*x*x***xxx##*#x
**#x##**xxx#####xx#x
#x###x#xx###xxx#####
x#xx##x####x##x#x#x#
#xx#########x#x#xx##
##x#xx#x#x###x#x###x
##x########xx###x##x
##xx##xxx##x##xx#x##
#xx#####x##x#x###x##
x#x#xx#xxx#x#xxx#x#x
###x###x#xx##x###x#x
...

output:

15

result:

ok 1 number(s): "15"

Test #4:

score: 10
Accepted
time: 1ms
memory: 7716kb

input:

31 20
*###**#*xxxxx**x**x#
x#***xxxxx*##**xx#x*
****x#xx#x*x***##*x#
#xx##xx##xx#*##x#***
#x##**#x*#x##*xxx**x
#*****#x*x****#xx#xx
##*****#*#xxx#x###xx
##x####xxx##########
x###x##x##x##xx#x#x#
#x##xx#########x####
####x#xxx#x#x#xxx##x
##x#x##xx#######xx##
######x####x####xx##
##xxx#xx#x##x#####x#
...

output:

17

result:

ok 1 number(s): "17"

Test #5:

score: 10
Accepted
time: 1ms
memory: 7236kb

input:

31 20
xx**xxxx***#xx*#x*x#
*#x*x*xx*#*x*xxx##*x
xx#x*x###*####xx**#*
#*xxx*x####*##*#***#
###*xxxx#*#x*x*xx##x
xxx**x*#*x##*x*x##xx
#*###x*x*xx#*#x#*#*x
#*#xx**##x#x*#x****#
###*#xxx*#x#x#**##**
#xx#x**xxx*###x##x#x
*x*#xx#*x##xxx*##*#*
xx###xx#x#***x#x###*
*#**xx#*xx#**#*x#xxx
*x##x#x*xxx*#**x**#x
...

output:

48

result:

ok 1 number(s): "48"

Test #6:

score: 10
Accepted
time: 2ms
memory: 7512kb

input:

50 50
xx#x#xx##x*#*xx#*xxx#x###*#x##*x##xxx##*#x*xx*##x*
x#x#*#xx*xxxx*#*##xx##*x*#*xx##xx#**#*#*#*###x*xxx
*x#x#*#**x#**x#x#*#*xx#x#x#*xx#x#x##*x***x####xxx*
*#*x#xx#x#****x*#x#x*####x*x######x**#*x##**xxx*x*
#x#xx*#xx###*xx*#*x**#*#*###****x*#*x##xx*##x####x
###*#x#xx####xxxx*x**##xxx##x*x*#***##*...

output:

348

result:

ok 1 number(s): "348"

Test #7:

score: 10
Accepted
time: 1ms
memory: 6772kb

input:

50 50
*#xx#x#****#***##*#xx*xx*x##xxxx###x#**#*#**x##xx*
*x*x*#x*x#***xx#x##xxx#x*#x*xx#**##x**x#xx***###x#
x**x#*#xx#x*#****#x*xx*#x##*x#xx#x**#*#*#**#x##x#*
#*#*##x#*##xx#xxx****x#xxx*x#x#*x#x##x***xx##x#**x
##*#*####*#**#x*xx**###*#xxx#x#***x*x*x#x#xx##x*x#
*x**x*x#xxx#*#xx*xx**x*xx**x#*#xxxx*x#*...

output:

367

result:

ok 1 number(s): "367"

Test #8:

score: 10
Accepted
time: 2ms
memory: 7680kb

input:

50 50
xx###*#*xx*xx#x*x###x*#xx*x*#*#x*####xx**x*x***xx*
*####*x*#*x###x#*#x****#*x*#x*x#***x*xxxxx#*###**x
*#x#**x***#*xx*##xx*x****#x****##*#x#*#x**##*#xx##
*xxxxxxx*#*xxxx##xx***##x#****#*#*##x#xx****#*#*#x
##*#x###x*x*x#x*#*###x*#xxxx*#xx*#x**##x#x*x#**x##
x*****#x**#x#*****x*##x*#xxx*x#xxx###x*...

output:

354

result:

ok 1 number(s): "354"

Test #9:

score: 10
Accepted
time: 1ms
memory: 6632kb

input:

50 50
**************************************************
**************************************************
**************************************************
**************************************************
**************************************************
***************************************...

output:

50

result:

ok 1 number(s): "50"

Test #10:

score: 10
Accepted
time: 1ms
memory: 7424kb

input:

11 10
#******#*x
x**x*xx*#*
#*#xx*x#xx
#*xx*#*#*x
#x###*#*##
xx##x##x##
#xx#x#####
#x######xx
###x######
##xx#x##x#
x#######x#

output:

11

result:

ok 1 number(s): "11"