Going Home (hdu 1533 最小费用流)
2024-10-19 00:22:41
集训的图论都快结束了,我才看懂了最小费用流,惭愧啊。 = = 但是今天机械键盘到了,有弄好了自行车,好高兴\(^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 ;
}
最新文章
- Spring MVC过滤器-委派过滤器代理(DelegatingFilterProxy)
- yii2 sphinx Ajax搜索分页 关键词的缓存
- iOS 进阶 第一天(0323)
- Cocos2d-x 使用物理引擎进行碰撞检测
- Wpf中MediaElement循环播放
- poj1006---中国剩余定理
- 【.Net基础拾遗】适配器模式(Adapter)与多态
- flex居中
- linux ——shell 脚本
- 【mysql】编码问题
- vscode rn代码格式化配置
- mysql技巧:如果记录存在则更新/如果不存在则插入的三种处理方法
- 网页头部meta标签
- MSP430入门准备
- ace-socket-reconnect
- 使用别名访问MSSQL Express
- spring mvc与mybatis整合错误提示
- 【学习笔记】--- 老男孩学Python,day15 python内置函数大全,递归,二分法
- 3、JVM--垃圾回收期和内存分配策略(1)
- omnibus gitlab-ce安装
热门文章
- UVa 272 Tex Quotes --- 水题
- 文件的搜寻【转vbird】
- Python小白好教程
- Echarts通过Ajax实现动态数据加载
- Error using subsindex Function &#39;subsindex&#39; is not defined for values of class &#39;struct&#39;.
- 图中最短路径算法(Dijkstra算法)(转)
- Unity Shaders
- PCA和Softmax分类比较—Mnist与人脸数据集
- Python字典笔记
- Linux进程间通信-命名管道