集训的图论都快结束了,我才看懂了最小费用流,惭愧啊。 = = 但是今天机械键盘到了,有弄好了自行车,好高兴\(^o^)/~

其实也不是看懂,就会套个模板而已。。。。

这题最重要的就是一个:

多组输入一定要写个init()函数清空,并且输入的时候每次都要调用init()

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int INF=0x3f3f3f3f;
typedef long long LL;
#define PI(A) printf("%d\n",A)
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d%d",&(N),&(M))
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,b) for(int i=0;i<(b);i++)
#define Rep(i,a,b) for(int i=(a);i<=(b);i++)
#define reRep(i,a,b) for(int i=(a);i>=(b);i--)
const double EPS= 1e- ; /* ///////////////////////// C o d i n g S p a c e ///////////////////////// */ const int MAX_V= + ; ///小白书模板///////////////// ///PS:V(即顶点数)一定要赋值
///PS:以下多组输入,要初始化 struct edge
{
int to,cap,cost,rev;
}; int V; //顶点数
vector<edge> G[MAX_V];//图的邻接表
int dist[MAX_V]; //最短距离
int prevv[MAX_V],preve[MAX_V]; //最短路中的前驱节点和对应的边 //添加边和费用
void add_edge(int from,int to,int cap,int cost)
{
G[from].push_back((edge)
{
to,cap,cost,G[to].size()
});
G[to].push_back((edge)
{
from,,-cost,G[from].size()-
});
} //求解从s到t流量为f的最小费用流
//如果不能再增广就返回-1
int min_cost_flow(int s,int t,int f)
{
int res=;
while(f>)
{
fill(dist,dist+V+,INF);
dist[s]=;
bool updata=true;
while(updata)
{
updata=false;
for (int v=; v<V; v++)
{
if (dist[v]==INF) continue; for(int i=; i<G[v].size(); i++)
{
edge &e=G[v][i];
if (e.cap>&&dist[e.to]>dist[v]+e.cost)
{
dist[e.to]=dist[v]+e.cost;
prevv[e.to]=v;
preve[e.to]=i;
updata=true;
}
}
}
} if (dist[t]==INF)
{
//不能在增广
return -;
}
int d=f;
for (int v=t; v!=s; v=prevv[v])
{
d=min(d,G[prevv[v]][preve[v]].cap); }
f-=d;
res+=d*dist[t];
for (int v=t; v!=s; v=prevv[v])
{
edge &e=G[prevv[v]][preve[v]];
e.cap-=d;
G[v][e.rev].cap+=d; }
}
return res;
}
///end///////////////// char ditu[MAX_V][MAX_V];
int N,M; int main()
{
#ifndef ONLINE_JUDGE
freopen("C:\\Users\\Zmy\\Desktop\\in.txt","r",stdin);
// freopen("C:\\Users\\Zmy\\Desktop\\out.txt","w",stdout);
#endif while(~SII(N,M),N||M)
{ cle(ditu,);
rep(i,N)
{
scanf("%s",ditu[i]);
} int numm=;
rep(i,N)
rep(j,M)
if (ditu[i][j]=='m')
{
numm++;
} int cntm=,cntH=numm+;
rep(i,N)
{
rep(j,M)
{
if (ditu[i][j]=='m')
{
cntH=numm+;
rep(i2,N)
{
rep(j2,M)
{
if (ditu[i2][j2]=='H')
{
add_edge(cntm,cntH,,abs(i-i2)+abs(j-j2));
// printf("cntm=%d cntH=%d\n",cntm,cntH);
// printf("cost=%d\n",abs(i-i2)+abs(j-j2));
cntH++; }
}
}
cntm++; }
}
} for (int i=;i<cntm;i++)
{
add_edge(,i,,);
// printf("0->%d\n",i);
}
for (int i=numm+;i<=*numm;i++)
{
add_edge(i,*numm+,,);
// printf("%d->%d\n",i,2*numm+1);
}     //这的V一定要赋值
V=*numm+;
/**< 一定要初始化 */
cle(prevv,);
cle(preve,); int ans=min_cost_flow(,*numm+,numm); PI(ans); /**< 一定要初始化 以后就用一个init都初始化了*/
for (int i=;i<MAX_V;i++)
{
G[i].clear();
} } return ;
}

最新文章

  1. Spring MVC过滤器-委派过滤器代理(DelegatingFilterProxy)
  2. yii2 sphinx Ajax搜索分页 关键词的缓存
  3. iOS 进阶 第一天(0323)
  4. Cocos2d-x 使用物理引擎进行碰撞检测
  5. Wpf中MediaElement循环播放
  6. poj1006---中国剩余定理
  7. 【.Net基础拾遗】适配器模式(Adapter)与多态
  8. flex居中
  9. linux ——shell 脚本
  10. 【mysql】编码问题
  11. vscode rn代码格式化配置
  12. mysql技巧:如果记录存在则更新/如果不存在则插入的三种处理方法
  13. 网页头部meta标签
  14. MSP430入门准备
  15. ace-socket-reconnect
  16. 使用别名访问MSSQL Express
  17. spring mvc与mybatis整合错误提示
  18. 【学习笔记】--- 老男孩学Python,day15 python内置函数大全,递归,二分法
  19. 3、JVM--垃圾回收期和内存分配策略(1)
  20. omnibus gitlab-ce安装

热门文章

  1. UVa 272 Tex Quotes --- 水题
  2. 文件的搜寻【转vbird】
  3. Python小白好教程
  4. Echarts通过Ajax实现动态数据加载
  5. Error using subsindex Function &#39;subsindex&#39; is not defined for values of class &#39;struct&#39;.
  6. 图中最短路径算法(Dijkstra算法)(转)
  7. Unity Shaders
  8. PCA和Softmax分类比较—Mnist与人脸数据集
  9. Python字典笔记
  10. Linux进程间通信-命名管道