[BZOJ 1412] 狼与羊的故事
2024-09-23 02:42:58
Link:
Solution:
非常明显的最小割模型:
将所有点分成两个互不相邻的点集,且要求代价最小
建图:
$<S,sheep,INF>$
$<wolf,T,INF>$
$<sheep,wolf/ground,1>$、$<ground,wolf/sheep/ground,1>$
Code:
#include <bits/stdc++.h> using namespace std;
const int MAXN=,MAXM=,INF=<<;
namespace Max_Flow
{
int head[MAXN],S,T,level[MAXN],iter[MAXN],tot=-;
struct edge{int nxt,to,cap;}e[MAXM<<]; void add_edge(int from,int to,int cap)
{
e[++tot].nxt=head[from];e[tot].to=to;e[tot].cap=cap;head[from]=tot;
e[++tot].nxt=head[to];e[tot].to=from;e[tot].cap=;head[to]=tot;
}
bool bfs()
{
memset(level,-,sizeof(level));
queue<int> q;q.push(S);level[S]=;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i!=-;i=e[i].nxt)
if(e[i].cap && level[e[i].to]==-)
level[e[i].to]=level[u]+,q.push(e[i].to);
}
return (level[T]!=-);
}
int dfs(int v,int f)
{
if(v==T) return f;
int ret=;
for(int &i=iter[v];i!=-;i=e[i].nxt)
{
if(level[e[i].to]==level[v]+ && e[i].cap)
{
int d=dfs(e[i].to,min(f,e[i].cap));
e[i].cap-=d;e[i^].cap+=d;
f-=d;ret+=d;if(!f) break;
}
}
return ret;
}
int Dinic()
{
int ret=;
while(bfs())
{
for(int i=;i<MAXN;i++) iter[i]=head[i];
ret+=dfs(S,INF);
}
return ret;
}
} int dx[]={,-,,},dy[]={,,,-};
int n,m,dat[][]; int main()
{
using namespace Max_Flow;
S=;T=;memset(head,-,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&dat[i][j]); for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(dat[i][j]==) add_edge(S,(i-)*m+j,INF);
if(dat[i][j]==){add_edge((i-)*m+j,T,INF);continue;}
for(int k=;k<;k++)
{
int fx=i+dx[k],fy=j+dy[k];
if(fx<||fx>n||fy<||fy>m) continue;
if(dat[i][j]!= || dat[fx][fy]!=)
add_edge((i-)*m+j,(fx-)*m+fy,);
}
}
printf("%d",Dinic());
return ;
}
最新文章
- 《Unix网络编程》卷一(简介TCP/IP、基础套接字编程)
- Static Const
- css2图片边框
- Ubuntu 16.04 Mxnet CPU 版本安装
- System.Data.OracleClient requires Oracle client software version 8.1.7 or greater
- POJ 1146 ID Codes (UVA146)
- LeetCode Same Tree (判断相同树)
- 高灵活低耦合Adapter快速开发攻略
- hh monitor
- Charle抓包与wireshark使用
- 书籍推荐系列之一 -- 《凤凰项目:一个IT运维的传奇故事》
- Eclipse使用Maven搭建Java Web项目,并直接部署Tomcat
- nginx 301重定向一种实现方法
- 使用OPEN XML SDK 读取EXCEL中的超链接Hyperlink
- sho
- 在PHP5.4上使用Google翻译的API报错
- 【转】iOS 自动化性能采集
- BadgeView 圆形数字提醒 购物车常用
- 实战分析: MySQL字符集
- 微软、谷歌、亚马逊、Facebook等硅谷大厂91个开源软件盘点(附下载地址)