为什么会T掉3个点?

P3355 骑士共存问题

walk_alone @ 2018-10-30 20:55:27

感觉没什么问题

#include <cstdio>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;
const int maxn=999999999;
struct line
{
    int from;
    int to;
    int v;
    int next;
};
line que[400001];
int headers[40050],depth[40050],cnt,n;
bool book[201][201];
int nexto[8][2]={{1,2},
                 {2,1},
                 {2,-1},
                 {-1,2},
                 {1,-2},
                 {-2,1},
                 {-1,-2},
                 {-2,-1}};
int cal(int x,int y)
{
    return n*(x-1)+y;
}
void add(int from,int to,int v)
{
    que[cnt].from=from;
    que[cnt].to=to;
    que[cnt].v=v;
    que[cnt].next=headers[from];
    headers[from]=cnt;
    cnt++;
}
bool bfs(int s,int t)
{
    memset(depth,0,sizeof(depth));
    queue<int>q;
    q.push(s);
    depth[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=headers[u];i!=-1;i=que[i].next)
            if(!depth[que[i].to] && que[i].v>0)
            {
                depth[que[i].to]=depth[u]+1;
                q.push(que[i].to);
            }
    }
    return depth[t]!=0;
}
int dfs(int u,int t,int flow)
{
    if(u==t || flow<=0)
        return flow;
    for(int i=headers[u];i!=-1;i=que[i].next)
        if(depth[que[i].to]==depth[u]+1)
        {
            int d=dfs(que[i].to,t,min(flow,que[i].v));
            if(d>0)
            {
                que[i].v-=d;
                que[i^1].v+=d;
                return d;
            }
        }
    return 0;
}
int dinic(int s,int t)
{
    int ans=0;
    while(bfs(s,t))
        while(int d=dfs(s,t,maxn))
            ans+=d;
    return ans;
}
int main()
{
    int a,b,s=0,t,m;
    scanf("%d%d",&n,&m);
    t=n*n+1;
    memset(headers,-1,sizeof(headers));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        book[a][b]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(book[i][j])
                continue;
            if((i+j)&1)
            {
                add(s,cal(i,j),1);
                add(cal(i,j),s,0);
                for(int o=0;o<=7;o++)
                {
                    int tx=i+nexto[o][0];
                    int ty=j+nexto[o][1];
                    if(tx<1 || ty<1 || tx>n || ty>n || book[tx][ty])
                        continue;
                    add(cal(i,j),cal(tx,ty),maxn);
                    add(cal(tx,ty),cal(i,j),0);
                }
            }
            else
            {
                add(cal(i,j),t,1);
                add(t,cal(i,j),0);
            }
         }
    printf("%d",n*n-m-dinic(s,t));
    return 0;
}

by Bobh @ 2018-10-30 20:56:07

%%%%%


by wuyuema @ 2018-10-30 20:56:11

%%%%%


by Brandon鹏 @ 2018-10-30 20:56:28

@walk_alone FYT大佬怎么可能有什么问题???


by wuyuema @ 2018-10-30 20:56:30

膜你


by wuyuema @ 2018-10-30 20:56:47

FYT:我这么弱


by walk_alone @ 2018-10-30 20:56:51

@Brandon鹏 哪有您神仙强


by Polaris1087 @ 2018-10-30 20:57:17

你们又开始了sro


by 追风の裙子桑 @ 2018-10-30 20:58:13

%%%

|