自闭患者求救

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 _Herobrine_ @ 2020-03-30 18:39:27

前排Orz大佬


by xiaoyaowudi @ 2020-03-30 18:40:09

点数超了吧


by xiaoyaowudi @ 2020-03-30 18:41:19

4e4个点


by cz2009 @ 2020-03-30 18:41:27

让kkk来解决


by do_while_false @ 2020-03-30 18:44:47

求助kkk


by Scherzo @ 2020-03-30 18:49:54

标题党,jbl


by Flandre_495 @ 2020-03-30 18:51:21

送您表情/kk/kk/kk/kk/kk/kk/kk/kk


by UnyieldingTrilobite @ 2020-03-30 19:11:05

惊现CSPS400+!


by metaphysis @ 2020-03-30 19:55:19

@Roden

您能解释一下您建立流网络的逻辑吗?从代码来看似乎有些奇怪。


by Roden @ 2020-03-30 20:33:47

@metaphysis 奇数点:原点(0)向其连一条1边,向能踩到的偶数点连INF边。 偶数点:向汇点连边。 貌似没问题


| 下一页