博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ3057 Evacuation(二分图最大匹配)
阅读量:5040 次
发布时间:2019-06-12

本文共 1853 字,大约阅读时间需要 6 分钟。

人作X部;把门按时间拆点,作Y部;如果某人能在某个时间到达某门则连边。就是个二分图最大匹配。

时间可以二分枚举,或者直接从1枚举时间然后加新边在原来的基础上进行增广。

 

谨记:时间是个不可忽视的维度。

1 #include
2 #include
3 #include
4 #include
5 using namespace std; 6 #define INF (1<<30) 7 #define MAXN 80000 8 #define MAXM 80000*400 9 10 struct Edge{ 11 int v,cap,flow,next; 12 }edge[MAXM]; 13 int vs,vt,NE,NV; 14 int head[MAXN]; 15 16 void addEdge(int u,int v,int cap){ 17 edge[NE].v=v; edge[NE].cap=cap; edge[NE].flow=0; 18 edge[NE].next=head[u]; head[u]=NE++; 19 edge[NE].v=u; edge[NE].cap=0; edge[NE].flow=0; 20 edge[NE].next=head[v]; head[v]=NE++; 21 } 22 23 int level[MAXN]; 24 int gap[MAXN]; 25 void bfs(){ 26 memset(level,-1,sizeof(level)); 27 memset(gap,0,sizeof(gap)); 28 level[vt]=0; 29 gap[level[vt]]++; 30 queue
que; 31 que.push(vt); 32 while(!que.empty()){ 33 int u=que.front(); que.pop(); 34 for(int i=head[u]; i!=-1; i=edge[i].next){ 35 int v=edge[i].v; 36 if(level[v]!=-1) continue; 37 level[v]=level[u]+1; 38 gap[level[v]]++; 39 que.push(v); 40 } 41 } 42 } 43 44 int pre[MAXN]; 45 int cur[MAXN]; 46 int ISAP(){ 47 bfs(); 48 memset(pre,-1,sizeof(pre)); 49 memcpy(cur,head,sizeof(head)); 50 int u=pre[vs]=vs,flow=0,aug=INF; 51 gap[0]=NV; 52 while(level[vs]
que;100 que.push(s);101 while(!que.empty()){102 x=que.front()/m; y=que.front()%m;103 for(int i=0; i<4; ++i){104 int nx=x+dx[i],ny=y+dy[i];105 if( nx<0||nx>=n||ny<0||ny>=m || map[nx][ny]!='.' || d[s][nx*m+ny] ) continue;106 d[s][nx*m+ny]=d[s][que.front()]+1;107 vis[nx*m+ny]=1;108 que.push(nx*m+ny);109 }110 que.pop();111 }112 }113 bool canEscape(){114 for(int i=0; i

 

转载于:https://www.cnblogs.com/WABoss/p/4855539.html

你可能感兴趣的文章
(转)面向对象最核心的机制——动态绑定(多态)
查看>>
token简单的使用流程。
查看>>
django创建项目流程
查看>>
UIActionSheet 修改字体颜色
查看>>
Vue 框架-01- 入门篇 图文教程
查看>>
Spring注解之@Lazy注解,源码分析和总结
查看>>
多变量微积分笔记24——空间线积分
查看>>
Magento CE使用Redis的配置过程
查看>>
poi操作oracle数据库导出excel文件
查看>>
(转)Intent的基本使用方法总结
查看>>
Mac 下的Chrome 按什么快捷键调出页面调试工具
查看>>
Windows Phone开发(24):启动器与选择器之发送短信
查看>>
JS截取字符串常用方法
查看>>
Google非官方的Text To Speech和Speech Recognition的API
查看>>
stdext - A C++ STL Extensions Libary
查看>>
Django 内建 中间件组件
查看>>
bootstrap-Table服务端分页,获取到的数据怎么再页面的表格里显示
查看>>
进程间通信系列 之 socket套接字及其实例
查看>>
天气预报插件
查看>>
Unity 游戏框架搭建 (十三) 无需继承的单例的模板
查看>>