QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#561000#9224. Express EvictionAfterlife#WA 0ms39592kbC++172.6kb2024-09-12 19:24:522024-09-12 19:24:53

Judging History

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

  • [2024-09-12 19:24:53]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:39592kb
  • [2024-09-12 19:24:52]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+1e3+7;

struct Edge{
    int ne,to,w;
}edg[N*2+1];

int cnt=1,head[N],hd[N];

void build(int u,int v,int w)
{
    ++cnt;
    edg[cnt].to=v;
    edg[cnt].ne=head[u];
    edg[cnt].w=w;
    head[u]=cnt;
    ++cnt;
    edg[cnt].to=u;
    edg[cnt].ne=head[v];
    edg[cnt].w=0;
    head[v]=cnt;
}

queue<int> q;

int d[N],S,T;

bool bfs()
{
    fill(d+S,d+T+1,-1);
    d[S]=0;
    q.push(S);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        hd[x]=head[x];
        for(int tmp=head[x];tmp;tmp=edg[tmp].ne)
        {
            int v=edg[tmp].to;
            if(d[v]!=-1||!edg[tmp].w)
                continue;
            d[v]=d[x]+1;
            q.push(v);
        }
    }
    return d[T]!=-1;
}

int dinic(int x,int mn)
{
    if(!mn||x==T)
        return mn;
    int flow=0,tmpf;
    for(int &tmp=hd[x];tmp;tmp=edg[tmp].ne)
    {
        int v=edg[tmp].to;
        if(d[v]==d[x]+1&&(tmpf=dinic(v,min(mn,edg[tmp].w)))>0)
        {
            flow+=tmpf;
            mn-=tmpf;
            edg[tmp].w-=tmpf;
            edg[tmp^1].w+=tmpf;
        }
        if(!mn)
            break;
    }
    return flow;
}

int n,m;

string s[N];

int gid(int x,int y,int i)
{
    return (x-1)*m+y+(i-1)*n*m;
}

int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    S=0,T=n*m*4+1;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]=' '+s[i];
    }
    //1:in 2:out 3:(0) 4:(1)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            build(gid(i,j,1),gid(i,j,2),1e9);
            build(gid(i,j,2),gid(i,j,3),1e9);
            build(gid(i,j,3),gid(i,j,4),s[i][j]=='#');
            build(gid(i,j,4),gid(i,j,1),1e9);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int d=0;d<4;d++)
            {
                int k=i+dx[d],l=j+dy[d];
                if(k<1||k>n||l<1||l>m)
                    continue;
                build(gid(i,j,2),gid(k,l,3),1e9);
                build(gid(i,j,4),gid(k,l,1),1e9);
            }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]!='#')
                continue;
            if(j==1||i==n)
                build(S,gid(i,j,3),1e9);
            if(j==m||i==1)
                build(gid(i,j,4),T,1e9);
        }
    int ans=0;
    while(bfs())
        ans+=dinic(S,1e9);
    cout<<ans<<"\n";
}
/*
6 4
..#.
###.
#...
....
...#
....
*/

详细

Test #1:

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

input:

4 6
.##...
.#....
##....
....#.

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 39592kb

input:

20 30
...###########################
#..###########################
...###########################
...###########################
.#############################
...###########################
...###########################
#..###########################
...###########################
..#...............

output:

7

result:

wrong answer 1st numbers differ - expected: '11', found: '7'