[Cogs14] [网络流24题#1] 飞行员分配方案 [网络流,最大流,二分图匹配]
2024-08-27 04:04:51
经典二分图匹配,可以用匈牙利算法,也可以用最大流
代码如下(Dinic):
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <queue> using namespace std; template<const int _n>
struct Edge
{
struct Edge_base { int to,next,w; }e[_n]; int p[_n],cnt;
void insert(const int x,const int y,const int z)
{ e[++cnt].to=y; e[cnt].next=p[x]; e[cnt].w=z; p[x]=cnt; return ; }
int start(const int x) { return p[x]; }
void clear() { cnt=;memset(p,,sizeof(p)); }
Edge_base& operator[](const int x) { return e[x]; }
}; int n,m,flow,SSS,TTT;
int level[],From[],From_e[];
Edge<> e; bool Bfs(const int S)
{
int i,t;
queue<int> Q;
memset(level,,sizeof(level));
memset(From,,sizeof(From));
level[S]=;
Q.push(S);
while(!Q.empty())
{
t=Q.front(),Q.pop();
for(i=e.start(t);i;i=e[i].next)
{
if(!level[e[i].to] && e[i].w)
{
level[e[i].to]=level[t]+;
Q.push(e[i].to);
From[e[i].to]=t;
From_e[e[i].to]=i;
if(e[i].to==TTT)goto End;
}
}
}
End:
if(!level[TTT])return false;
flow++;
for(i=TTT;i!=SSS;i=From[i])e[From_e[i]].w--,e[From_e[i]^].w++;
return true;
} int Dinic()
{
while(Bfs(SSS));
return flow;
} int main()
{
freopen("flyer.in","r",stdin);
freopen("flyer.out","w",stdout); int i,x,y; scanf("%d%d",&m,&n);
m=m-n;
while(scanf("%d%d",&x,&y)==)
{
if(x>y)swap(x,y);
e.insert(x,y,);
e.insert(y,x,);
} SSS=n+m+,TTT=n+m+;
for(i=;i<=n;++i)
{
e.insert(SSS,i,);
e.insert(i,SSS,);
}
for(i=n+;i<=m+n;++i)
{
e.insert(i,TTT,);
e.insert(TTT,i,);
} printf("%d\n",Dinic()); return ;
}
匈牙利代码:http://www.cnblogs.com/Ngshily/p/4988909.html
最新文章
- Map的性能
- Easy Tag Write(2)
- CentOS下apache绑定域名
- 怎么通过 Microsof Office Project 2010 来写功能开发计划
- WCF TCP 错误代码 10061: 由于目标计算机积极拒绝
- noip2008 笨小猴
- 1025: [SCOI2009]游戏 - BZOJ
- ADB命令与monkey
- Genymotion中SD卡目录在Eclipse中查看,以及创建SDCard
- 我的Python成长之路---第三天---Python基础(12)---2016年1月16日(雾霾)
- bc38 1002, bc39 1002
- Linux基础命令操作实例
- POJ3624--01背包
- 转-python中的闭包
- AndroidStudio 集成litepal 报错
- tp5.1中的容器和facade的实现
- C#批量向数据库插入数据
- 深入浅出Java反射
- Mudo C++网络库第十章学习笔记
- c++第十四天
热门文章
- [Swift通天遁地]三、手势与图表-(9)制作五彩缤纷的气泡图表
- SS配置,Brook是什么?,Brook如何配置(Android篇)
- 关于网页的自适应问题一---Media Query(媒介查询)
- linux 怎么在后台添加运行脚本,即使关机也可以用
- Servlet到Servlet的请求转发与重定向的区别
- [转]linux之cut命令的用法
- cocos2d-js 开发常见问题
- C语言关键字之sizeof
- Android RecyclerView遇到notifyDataSetChanged无效时的解决方案
- 获取Google地图位置坐标并嵌入到网页