闲扯
今天上课将网络流例题，难得的想出怎么建图的几个题之一。。
题面
Solution
因为只有羊和狼两种生物，且不能分到同一个集合中，所以可以建立二分图。而我们要用最少的篱笆，将狼和羊分开，考虑最小割。
虚拟一个超级源点，连向所有是狼的格子，流量为 (INF) ，表示这个边不能割。
虚拟一个超级汇点，将所有是羊的格子连向它，流量为 (INF) ，理由同上。
然后对于每一个格子，向他的四周连一条流量为 (1) 的边，表示在这两个格子之间修一个篱笆，费用为 (1) 。
当然，如果相邻两个格子都是狼或者都是羊，就不用连了，因为没必要在这里修篱笆。
然后跑最小割，每条割边表示在这里修一个篱笆。
正确性：对于所有的狼、羊，都是连着源点、汇点的，流量为 (INF) ，一定不会割这些边，而狼和羊、空格子连边代表篱笆，这个图的最小割集使得该图分为只含狼、只含羊的两个集合，也就满足了题意。
Code
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
int f=1;char k=getchar();x=0;
for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
x*=f;
}
template<class T>il print(T x){
if(x/10) print(x/10);
putchar(x%10+'0');
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
int res=1,bas=x%mod;
while(m){
if(m&1) res=(res*bas)%mod;
bas=(bas*bas)%mod,m>>=1;
}
return res%mod;
}
const int MAXN = 105;
int n,m,s,t,val[MAXN][MAXN],cur[MAXN*MAXN],head[MAXN*MAXN],num_edge=-1,dis[MAXN*MAXN];
struct Edge{
int next,to,w;
Edge(){}
Edge(int next,int to,int w):next(next),to(to),w(w){}
}edge[MAXN*MAXN*9];
il add_edge(int u,int v,int w){
edge[++num_edge]=Edge(head[u],v,w),head[u]=num_edge;
edge[++num_edge]=Edge(head[v],u,0),head[v]=num_edge;
}
inl bool BFS(int s,int t){
del(dis,0),dis[s]=1;
queue<int> q;q.push(s);
while(!q.empty()){
ri pos=q.front();q.pop();
for(ri i=head[pos];i!=-1;i=edge[i].next)
if(!dis[edge[i].to]&&edge[i].w>0){
dis[edge[i].to]=dis[pos]+1;
if(edge[i].to==t) return true;
q.push(edge[i].to);
}
}
return false;
}
it DFS(int now,int t,int flow){
if(now==t) return flow;
ri s=0,k;
for(ri &i=cur[now];i!=-1;i=edge[i].next)
if(dis[edge[i].to]==dis[now]+1&&edge[i].w>0){
k=DFS(edge[i].to,t,min(flow-s,edge[i].w));
s+=k,edge[i].w-=k,edge[i^1].w+=k;
if(s==flow) break;
}
if(s==0) dis[now]=0;
return s;
}
it Dinic(int s,int t){
ri res=0;
while(BFS(s,t)){
memcpy(cur,head,sizeof(head));
res+=DFS(s,t,INF);
}
return res;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m),del(head,-1),t=n*m+1;
for(ri i=1;i<=n;++i)
for(ri j=1;j<=m;++j)
read(val[i][j]);
for(ri i=1;i<=n;++i)
for(ri j=1;j<=m;++j){
if(val[i][j]==1) add_edge(s,(i-1)*m+j,INF);
if(val[i][j]==2) add_edge((i-1)*m+j,t,INF);
if(i!=1&&(val[i][j]!=val[i-1][j]||!val[i][j])) add_edge((i-1)*m+j,(i-2)*m+j,1);
if(i!=n&&(val[i][j]!=val[i+1][j]||!val[i][j])) add_edge((i-1)*m+j,i*m+j,1);
if(j!=1&&(val[i][j]!=val[i][j-1]||!val[i][j])) add_edge((i-1)*m+j,(i-1)*m+j-1,1);
if(j!=m&&(val[i][j]!=val[i][j+1]||!val[i][j])) add_edge((i-1)*m+j,(i-1)*m+j+1,1);
}
printf("%d",Dinic(s,t));
return 0;
}
总结
这应该是一个比较简单的最小割的题吧，建图比较明显，看到两种不同的东西，不能分在一起，可以往这方面联想一下。