题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=1533

#include<bits/stdc++.h>
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pqueue priority_queue
#define NEW(a,b) memset(a,b,sizeof(a))
const double pi=4.0*atan(1.0);
const double e=exp(1.0);
const int maxn=1e6+;
typedef long long LL;
typedef unsigned long long ULL;
const LL mod=1e9+;
const ULL base=1e7+;
using namespace std;
struct edge{
int to,nxt,flow,cost;
}g[maxn];
int head[],pre[],dis[],cnt,s,t,tot;
int a[][];
bool vis[];
char ss[];
void add(int x,int y,int cost,int flow){
g[cnt].to=y;
g[cnt].nxt=head[x];
g[cnt].cost=cost;
g[cnt].flow=flow;
head[x]=cnt++;
}
bool spfa(){
memset(pre,-,sizeof(pre));
memset(dis,INF,sizeof(dis));
memset(vis,,sizeof(vis));
queue<int> que;
while(!que.empty()){que.pop();}
que.push(s);
dis[s]=;
vis[s]=;
while(!que.empty()){
int k=que.front();
que.pop();
vis[k]=;
int tt=head[k];
while(tt!=-){
if(dis[g[tt].to]>dis[k]+g[tt].cost&&g[tt].flow>){
pre[g[tt].to]=tt;
dis[g[tt].to]=dis[k]+g[tt].cost;
if(vis[g[tt].to]==){
que.push(g[tt].to);
vis[g[tt].to]=;
}
}
tt=g[tt].nxt;
}
}
return pre[t]!=-;
}
int maxflow(){
int ans=;
while(spfa()){
int f=INF;
for(int i=pre[t];i!=-;i=pre[g[i^].to]){
if(g[i].flow<f)
f=g[i].flow;
}
for(int i=pre[t];i!=-;i=pre[g[i^].to]){
g[i].flow-=f;
g[i^].flow+=f;
ans+=g[i].cost*f;
}
}
return ans;
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF&&n&&m){
memset(head,-,sizeof(head));
cnt=tot=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
a[i][j]=tot++;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(j!=m){
add(a[i][j],a[i][j+],,INF);
add(a[i][j+],a[i][j],-,);
add(a[i][j+],a[i][j],,INF);
add(a[i][j],a[i][j+],-,);
}
if(i!=n){
add(a[i][j],a[i+][j],,INF);
add(a[i+][j],a[i][j],-,);
add(a[i+][j],a[i][j],,INF);
add(a[i][j],a[i+][j],-,);
}
}
}
s=tot++;
t=tot++;
for(int i=;i<=n;i++){
scanf("%s",ss);
for(int j=;j<m;j++){
if(ss[j]=='H'){
add(a[i][j+],t,,);
add(t,a[i][j+],,);
}
if(ss[j]=='m'){
add(s,a[i][j+],,);
add(a[i][j+],s,,);
}
}
}
printf("%d\n",maxflow());
}
}

最新文章

  1. ajax和sap以及网络安全
  2. SQL Server 抛出自定义异常,由C#程序俘获之并进行相应的处理
  3. Android学习笔记之AndroidManifest.xml文件解析(转)
  4. netty socket 客服端编程
  5. Nginx提示502和504错误的解决方案
  6. poj3307
  7. ui线程和后台线程异步
  8. Xmpp实现简单聊天系列 --- ②用户注册和登陆
  9. 墨卡托投影坐标系(Mercator Projection)原理及实现C代码
  10. Socket.io应用之联网拖拽游戏
  11. 37.Spring-事务控制.md
  12. 上下文无关的GMM-HMM声学模型
  13. html 统一资源定位器(url)和url编码
  14. 删除一个cjson导致系统死机
  15. 分布式理论(三)—— 一致性协议之 2PC
  16. weblogic+eclipse插件部署多个项目
  17. plantuml使用教程【转】
  18. jquery.chosen.js下拉选择框美化插件项目实例
  19. advapi32.dll kernel32.dll 中的两套注册表API
  20. Codeforces Round #340 (Div. 2) A

热门文章

  1. 有人WIFI ble101配置
  2. .net webapi跨域方法整理
  3. 《JavaScript 设计模式与开发实战》第一部分(1、2、3章)笔记
  4. Python全栈之路----类型转换
  5. linux 命令失效
  6. ES5与ES6中的继承
  7. java-IO流-字符流-FileReader、FileWriter、自定义小数组的拷贝、BufferedReader、BufferedWriter、readLine()和newLine()方法、LineNumberReader、使用指定的码表读写字符
  8. Linux 文件查看,文件夹切换,权限查看
  9. randrange()和random() 函数
  10. LOJ 3059 「HNOI2019」序列——贪心与前后缀的思路+线段树上二分