QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#468604 | #6359. 游戏 | little_sun | 100 ✓ | 2ms | 7716kb | C++14 | 2.9kb | 2024-07-08 21:48:32 | 2024-07-08 21:48:33 |
Judging History
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"