自闭患者求救

P3355 骑士共存问题

Roden @ 2020-03-30 18:38:15

最大流部分没问题,应该是建模错了,但不知道哪里错了。导致MSVC、G++的结果都不一样。

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
#define MAX_V 10010
struct edge{int to,cap,rev;};
vector<edge> G[MAX_V];
void addedge(int from,int to,int cap)
{
    G[from].push_back(edge{to,cap,(int)G[to].size()});
    G[to].push_back(edge{from,0,(int)G[from].size()-1});
}
int level[MAX_V],iter[MAX_V];
int dfs(int v,int t,int f)
{
    if(v==t)return f;
    for(int &i=iter[v];i<G[v].size();i++)
    {
        edge &e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to])
        {
            int d=dfs(e.to,t,min(e.cap,f));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int max_flow(int s,int t)
{
    int flow=0;
    queue<int> que;
Label:
    memset(level,-1,sizeof(level));
    level[s]=0;
    que.push(s);
    while(!que.empty())
    {
        int v=que.front();que.pop();
        for(edge &e:G[v]){
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
    if(level[t]<0)return flow;
    memset(iter,0,sizeof(iter));
    int f;
    while((f=dfs(s,t,INF))>0)
        flow+=f;
    goto Label;
}
bool can[211][211];
const int dx[8]={1,1,-1,-1,2,2,-2,-2},dy[8]={2,-2,2,-2,1,-1,1,-1};
int main()
{
#ifndef ONLINE_JUDGE
    freopen("stdin.txt", "r", stdin);
#endif
    int n,m;
    scanf("%d%d",&n,&m);
    const int s=0,t=n*n+1;
    for(int i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        can[x][y]=true;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        if(can[i][j])continue;
        int index=i*n+j-n;
        if((i+j)&1){
            addedge(0,index,1);
            for(int k=0;k<8;k++)
            {
                int x=i+dx[i],y=j+dy[i];
                if(x>0&&x<=n&&y>0&&y<=n&&!can[x][y])
                    addedge(index,x*n+y-n,INF);
            }
        }else addedge(index,t,1);
    }
    printf("%d",n*n-m-max_flow(0,t));
    return 0;
}

by metaphysis @ 2020-03-30 22:48:29

@Roden

哎呀,一个低级错误啊!

int x=i+dx[i],y=j+dy[i];

by metaphysis @ 2020-03-30 23:50:10

@Roden

还有一个小问题,题目约束中n<=200,则应:

#define MAX_V 40010

较为妥当。

此外,建议您使用链式前向星来表示图,然后重新编写Dinic算法的实现,尽量清晰一些,以便作为自己的标准代码库使用。使用邻接表来表示图的实现看起来似乎有些别扭。


上一页 |