蒟蒻求助各位dalao,为啥第三个点T了

P3355 骑士共存问题

GoldenPotato137 @ 2018-01-29 12:20:36

RT,求dalao帮忙

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=200+30;
const int inf=0x3f3f3f3f;
struct road
{
    int w,to,opp;
};
vector <road> e[N*N];
bool mark[N][N];
int n,m,S=0,T=40960;
void AddLine(int s,int t,int w)
{
    road temp;
    temp.to=t,temp.w=w,temp.opp=e[t].size();
    e[s].push_back(temp);
    temp.to=s,temp.w=0,temp.opp=e[s].size()-1;
    e[t].push_back(temp);
}
inline int GetNum(int y,int x)
{
    return (y-1)*n+x;
}
int depth[N*N];
queue <int> q;
bool bfs()
{
    memset(depth,0,sizeof depth);
    q.push(S);
    while(!q.empty())
    {
        int now=q.front(),size=e[now].size();
        for(int i=0;i<size;i++)
            if(depth[e[now][i].to]==0 and e[now][i].w>0 and e[now][i].to!=S)
            {
                depth[e[now][i].to]=depth[now]+1;
                q.push(e[now][i].to);
            }
        q.pop();
    }
    return depth[T]==0?false:true;
}
int dfs(int now,int ans)
{
    if(now==T or ans==0) return ans;
    int size=e[now].size(),rec=0;
    for(int i=0;i<size;i++)
        if(e[now][i].w>0 and depth[e[now][i].to]==depth[now]+1)
        {
            int to=e[now][i].to,t_ans=dfs(to,min(ans-rec,e[now][i].w));
            e[now][i].w-=t_ans;
            e[to][e[now][i].opp].w+=t_ans;
            rec+=t_ans;
            if(rec==ans) break;
        }
    return rec;
}
int Dinic()
{
    int ans=0;
    while(bfs())
        ans+=dfs(S,inf);
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n*n;i++)
        e[i].reserve(16);
    for(int i=1;i<=m;i++)
    {
        int tx,ty;
        scanf("%d%d",&tx,&ty);
        mark[ty][tx]=true;
    }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!mark[i][j])
            {
                int now=(i-1)*n+j;
                if((i%2)==(j%2))//R
                    AddLine(S,now,1);
                else //Y
                    AddLine(now,T,1);
                if((i%2)!=(j%2)) continue;
                if(i-2>0 and j-1>0 and !mark[i-2][j-1]) AddLine(now,GetNum(i-2,j-1),inf);
                if(i-2>0 and j+1<=n and !mark[i-2][j+1]) AddLine(now,GetNum(i-2,j+1),inf);
                if(i-1>0 and j-2>0 and !mark[i-1][j-2]) AddLine(now,GetNum(i-1,j-2),inf);
                if(i-1>0 and j+2<=n and !mark[i-1][j+2]) AddLine(now,GetNum(i-1,j+2),inf);
                if(i+1<=n and j-2>0 and !mark[i+1][j-2]) AddLine(now,GetNum(i+1,j-2),inf);
                if(i+1<=n and j+2<=n and !mark[i+1][j+2]) AddLine(now,GetNum(i+1,j+2),inf);
                if(i+2<=n and j-1>0 and !mark[i+2][j-1]) AddLine(now,GetNum(i+2,j-1),inf);
                if(i+2<=n and j+1<=n and !mark[i+2][j+1]) AddLine(now,GetNum(i+2,j+1),inf);
            }

    printf("%d",n*n-m-Dinic());
    return 0;
}

by sermoon @ 2018-01-29 12:29:40

网络流跑太慢了。。。。。

用Dinic优化或者ISAP吧


|