QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#557132#2752. Neutral GroundTenshiAC ✓3ms6020kbC++202.6kb2024-09-11 04:40:502024-09-11 04:40:50

Judging History

This is the latest submission verdict.

  • [2024-09-11 04:40:50]
  • Judged
  • Verdict: AC
  • Time: 3ms
  • Memory: 6020kb
  • [2024-09-11 04:40:50]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
 
#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;

#define int ll
 
inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=45*45*2, M=1e5+5, INF=1e12+10;

int n, m, S, T;
int id[45][45], idx;
char g[45][45];
const int dx[]={-1, 1, 0, 0};
const int dy[]={0, 0, -1, 1};

struct Edge{
    int to, c, next;
}e[M<<1];

int h[N], tot;

void add(int u, int v, int c){
    e[tot].to=v, e[tot].c=c, e[tot].next=h[u], h[u]=tot++;
    e[tot].to=u, e[tot].c=0, e[tot].next=h[v], h[v]=tot++;  
}

int d[N], q[N], cur[N];

bool bfs(){
    memset(d, -1, sizeof d);
    int tt=-1, hh=0;
    q[++tt]=S, d[S]=0, cur[S]=h[S];

    while(tt>=hh){
        int hd=q[hh++];
        for(int i=h[hd]; ~i; i=e[i].next){
            int go=e[i].to;
            if(d[go]==-1 && e[i].c){
                d[go]=d[hd]+1;
                cur[go]=h[go];
                if(go==T) return true;
                q[++tt]=go;
            }
        }
    }
    return false;
}

int find(int u, int limit){
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u]; ~i && flow<limit; i=e[i].next){
        cur[u]=i;
        int go=e[i].to;
        if(d[go]==d[u]+1 && e[i].c){
            int t=find(go, min(e[i].c, limit-flow));
            if(!t) d[go]=-1;
            e[i].c-=t, e[i^1].c+=t, flow+=t;
        }
    }
    return flow;
}

int dinic(){
    int res=0, flow;
    while(bfs()) while(flow=find(S, INF)) res+=flow;
    return res;
}


int val(char c){
	if(isdigit(c)) return c-'0';
	return INF;
}

signed main(){
	memset(h, -1, sizeof h);
	cin>>n>>m;
	swap(n, m);
	S=0, T=2*n*m+1;
	rep(i, 1, n) rep(j, 1, m){
		cin>>g[i][j];
		id[i][j]=++idx;
	}
	
	rep(i, 1, n) rep(j, 1, m){
		add(id[i][j], id[i][j]+idx, val(g[i][j]));
		// add(id[i][j], id[i][j]+idx, INF, 0);
		if(g[i][j]=='A') add(S, id[i][j], INF);
		if(g[i][j]=='B') add(id[i][j]+idx, T, INF);
		rep(k, 0, 3){
			int ii=i+dx[k], jj=j+dy[k];
			if(!id[ii][jj]) continue;
			int u=id[i][j], v=id[ii][jj];
			if(g[i][j]=='A'){
				add(u+idx, v, INF);	
			}
			else if(g[i][j]!='B'){
				if(g[ii][jj]!='A'){
					add(u+idx, v, INF);
				}
			} 
		}
	}
	
	cout<<dinic()<<endl;
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3668kb

input:

8 5
A11111AA
AA7B111A
111BB111
11BBB111
11BBB11B

output:

13

result:

ok single line: '13'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

25 6
A211111321231111111111111
2A2111110001111111BB11111
AA211111000111111BBBB1111
A2111114111411111BBBB1111
AA2111110001111111BB11111
AA21111110111111111111111

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

10 10
9999999999
9999999999
9999999999
11B0999999
1000999999
1999999999
1999990999
199990A099
1999991999
1111111999

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 2ms
memory: 4096kb

input:

40 40
A111111111111111111111111111111111111111
1111111111111111111111111111111111111111
1111111111111111111111111111111111111111
111111111111111111111111111111111111111A
1111111111111111111111111111111111111111
1111111111111111111111111111111111111111
1111111111111111111111111111111111111111
1111111...

output:

25

result:

ok single line: '25'

Test #5:

score: 0
Accepted
time: 1ms
memory: 5904kb

input:

40 40
A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9
9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A
A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9
9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A
A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9
9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A
A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9A9B9
9B9A9B9...

output:

7200

result:

ok single line: '7200'

Test #6:

score: 0
Accepted
time: 0ms
memory: 6020kb

input:

40 40
A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0
0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A
A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0
0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A
A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0
0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A
A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0A0B0
0B0A0B0...

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 0ms
memory: 4152kb

input:

40 40
A111111111111111111111111111111111111111
1111111111111111111111111111111111111111
1111111111111111111111111111111111111111
111111111111111111111111111111111111111A
1111111111111111111111111111111111111111
1111111111111111111111111111111111111111
1111111111111111111111111111111111111111
1111111...

output:

27

result:

ok single line: '27'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

8 6
99999999
11B89999
19990009
19990A09
19999199
11111199

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

10 20
7436199416
0740828365
3BB97AAA56
BB1050A576
BB09AAAA59
9436A7A594
870752A305
17311AAA18
300778AA80
694AAAA920
829AA67466
9AAA816697
AAAA5BBB89
AAAA5BBB94
7AA6BBBB47
AAA5B0BBB0
2A0BB1BB05
372BB91B62
3595BBBBBB
357BBBBBB9

output:

56

result:

ok single line: '56'

Test #10:

score: 0
Accepted
time: 1ms
memory: 5700kb

input:

20 10
13BBBBB8683006374919
4BB2B237281364446735
BBB97700668962755468
B4428083260BB2086623
2AAAA777BBBBBBB49548
8AAAA9A5BBBBBBBBB202
AAAAAAA2BBBBBBBBB402
8AAAAAA69BBB3BB28218
AAAAAAA83BB38BBB3359
AAAAAAA7999455827606

output:

49

result:

ok single line: '49'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

20 20
25856295408107772399
35893013789856837104
39164180311582356777
42396356552896556340
87301639504573750650
36149965146808550936
46668126767624245842
81785A87739588198960
58978AAAA55552271341
449902AA133983981669
09702AAA415039084066
56057AAAA04537698341
10580AAAA7054BB87604
85998AAAA3815BBBB178
...

output:

47

result:

ok single line: '47'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3972kb

input:

30 20
83272382997532854470AAA2081085
55418167116020216737AAAA836122
08615309275630600141AAA3750137
10412727935316509926AAA8213842
946090169942907317670292352638
473669321729065940959047626928
966175998987030436453643678467
959428364139218626723848883353
360180877508819524157455721160
8B2465420154488...

output:

26

result:

ok single line: '26'

Test #13:

score: 0
Accepted
time: 2ms
memory: 4020kb

input:

35 35
71439710038840545765840866706615187
87011124136864908978528863143370418
72463503519784A64766554520801522357
67336355780600AA4A17316394465519317
40340535175910AAAAA4920444132787303
3887020407108748A6A8174316547499885
155219950383942AA5A1534978388940968
0348016997AA424AAA05188851894551568
861497...

output:

41

result:

ok single line: '41'

Test #14:

score: 0
Accepted
time: 3ms
memory: 4144kb

input:

40 40
0679221947731249959969433845432750656124
4379325056263218235062679461823907756941
8621910410306401844044524168766281673138
3112229466003110829374745773576090285698
0628020663404653026560929857657748975624
7663359924019535309405104891364250469737
0AA6694896753027751014062836968001610487
2396239...

output:

55

result:

ok single line: '55'