Eternity

Until The End

P2598 [ZJOI2009]狼和羊的故事

发表于 分类于
本文字数： 3.5k 阅读时长 ≈ 3 分钟

常见的最小割模型。

P2598 [ZJOI2009]狼和羊的故事

刚开始想的模型，似乎要更准确一些：

  • 链接 $(S,u,inf)$ ，其中 $u$ 为羊的地盘；
  • 链接 $(v,T,inf)$ ，其中 $v$ 为狼的地盘；
  • 链接 $(u,v,1)$ ，其中 $u,v$ 地盘所属不同；
  • 链接 $(u,v,1)$ ，其中 $u,v$ 有至少一块是空地。

然后过了。

刚开始并没有考虑 $0$ 的情况（因为没看见），然后直接飞起（后来发现并不是这里的锅）。但仔细想一想，空地在最后的划分方案里，既可以作为羊的地盘，也可以作为狼的地盘，所以无所谓，从而合并三四的情况。

然后没发现 getId(i,j) 写挂了，就去逛了一圈题解区，发现建图更暴力，直接往四周全部都连一遍，这样大大增加了边量，并加大了时间与空间的消耗（虽说网络流没有卡时空这一说），但我还是觉得这种方法是不理智的，不然到时候一个 $\textcolor{Blue}{\text{Memory Limit Exceeded}}$ 一出来，两行泪就不必多说了。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s!='\0') putchar(*s++);
}
template<>
inline void write(const char *s)
{
    while(*s!='\0') putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline void checkMax(T &x,T y)
{
    x=x>y?x:y;
}
template<class T>
inline void checkMin(T &x,T y)
{
    x=x<y?x:y;
}
const int MAXN=1e4+10,MAXE=1e6+10;
const int INF=0x3f3f3f3f;
const int dx[]={0,1,-1,0,0};
const int dy[]={0,0,0,1,-1};
int N,M,S,T;
struct Net
{
    int next,to,val;
}Edge[MAXE<<1];
int Head[MAXN],Cur[MAXN],Total=1;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=(Net){Head[u],v,w};Head[u]=Total;
    Edge[++Total]=(Net){Head[v],u,0};Head[v]=Total;
}
int Fl[MAXN];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    Cur[S]=Head[S],Fl[S]=0;
    std::queue<int>Q;
    Q.push(S);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[u]+1,Cur[v]=Head[v];
                if(v==T) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int x,int inf)
{
    if(x==T) return inf;
    int flow=0;
    for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
    {
        v=Edge[e].to,Cur[x]=e;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(v,std::min(Edge[e].val,inf-flow));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline int Dinic()
{
    int r=0,flow;
    while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
    return r;
}
inline int getId(int i,int j)
{
    return M*(i-1)+j;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,M);
    S=0,T=N*M+1;
    for(re int i=1;i<=N;++i)
        for(re int j=1,Mp;j<=M;++j)
        {
            read(Mp);
            if(Mp==1) addEdge(S,getId(i,j),INF);
            if(Mp==2) addEdge(getId(i,j),T,INF);
            for(re int k=1;k<=4;++k)
            {
                int nx=i+dx[k],ny=j+dy[k];
                if(nx<1||nx>N||ny<1||ny>M) continue;
                addEdge(getId(i,j),getId(nx,ny),1);
            }
        }
    write(Dinic());
    return 0;
}
/*
2 2
2 2 
1 1 
*/
相关文章