洛谷 P2756 飞行员配对方案问题
2018-09-01 05:38:29来源:博客园 阅读 ()
全名:线性规划与网络流24题
按照题目难度顺序:
1.飞行员配对方案问题(求最大匹配数并且输出配对方案)
两种做法:
1)二分图匹配匈牙利算法,可以直接求出最大匹配数,并且数组中记录了最佳配对方案
2)最大流,超级源点S到A集合中每一个元素建边(容量为1),B集合中每一个点到汇点建边(容量为1),A集合中与B集合中可匹配的点之间建边(容量为1),跑最大流即可得到最大匹配数.
由于Dinic算法中被使用过的路流量会减少,而它的反向边流量会增加.
所以在最大匹配的时候,AB集合中两个点若配对,有 A -> B的边容量为0 (或B -> A的边容量为1).
二分图匈牙利版本:
#include <bits/stdc++.h> using namespace std; #define N 105 #define M 20005 struct Edge{ int to,next; }edge[M]; int n,m; int vis[N],match[N],to[N],head[N];//初始化match -> -1 ,to -> 0 int cnt; void init(){ cnt = 0; memset(head,-1,sizeof(head)); memset(match,-1,sizeof(match)); memset(to,0,sizeof(to)); } bool dfs(int u){ for(int i = head[u];i != -1;i = edge[i].next){ int v = edge[i].to; if(!vis[v]){ vis[v] = 1; if(match[v] == -1 || dfs(match[v])){ match[v] = u; to[u] = v; return true; } } } return false; } //cnt 为最多匹配到的点数(单边点数) int hungry(){ cnt = 0; for(int i = 1;i <= n;++i){ memset(vis,0,sizeof(vis)); if(!to[i]) cnt += dfs(i); } return cnt; } int main() { init(); scanf("%d%d",&m,&n); int u,v; while(scanf("%d%d",&u,&v) && u != -1){ edge[cnt].to = v,edge[cnt].next = head[u],head[u] = cnt++; } printf("%d\n",hungry()); for(int i = 1;i <= m;++i) if(to[i]) printf("%d %d\n",i,to[i]); return 0; }
最大流dinic版本:
//最大流Dinic算法 //m为边数,n为点数 //复杂度O(m*n*n) #include <bits/stdc++.h> using namespace std; #define N 105 #define M 20005 int INF = 0x3f3f3f3f; int dep[N],head[N]; int to[N];//当前弧优化 int n,m; struct Edge{ int to,next,w; }edge[M<<1]; int cnt = 0; //edge[i] 的反向边为 dege[i^1] int s,t;//s->源,t->汇 void ad(int x,int y,int w){ edge[cnt].to = y,edge[cnt].next = head[x],edge[cnt].w = w,head[x] = cnt++; edge[cnt].to = x,edge[cnt].next = head[y],edge[cnt].w = 0,head[y] = cnt++; } void init(){ memset(to,0,sizeof(to)); memset(head,-1,sizeof(head)); cnt = 0; } bool D_bfs(){ memset(dep,0,sizeof(dep)); memset(to,0,sizeof(to)); dep[s] = 1; queue<int> Q; while(!Q.empty()) Q.pop(); Q.push(s); while(!Q.empty()){ int u = Q.front(); Q.pop(); for(int i = head[u];i != -1;i = edge[i].next){ int v = edge[i].to; if(edge[i].w > 0 && !dep[v]){ dep[v] = dep[u] + 1; Q.push(v); } } } if(dep[t]) return 1; return 0; } int D_dfs(int u,int now){ if(u == t) return now; int beg = to[u] ? to[u] : head[u]; for(int i = beg;i != -1;i = edge[i].next){ int v = edge[i].to; if(dep[v] == dep[u] + 1 && edge[i].w > 0){ int di = D_dfs(v,min(now,edge[i].w)); if(di == 0) continue; edge[i].w -= di; edge[i^1].w += di; if(edge[i].w) to[u] = i; else to[u] = edge[i].next; return di; } } return 0; } int Dinic(){ int sum = 0,flow; while(D_bfs()){ while((flow = D_dfs(s,INF))) sum += flow; } return sum; } int l , r; void getMap(){ scanf("%d%d",&m,&n); s = 0,t = n+1; for(int i = 1;i <= m;++i) ad(0,i,1); for(int i = m+1;i <= n;++i) ad(i,n+1,1); int u,v; l = cnt; while(scanf("%d%d",&u,&v) && u != -1) ad(u,v,1); r = cnt; } int main() { init(); getMap(); printf("%d\n",Dinic()); for(int i = l;i < r;i += 2){ if(edge[i].w == 0){ printf("%d %d\n",edge[i^1].to,edge[i].to); } } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷P1164->小A点菜 2020-05-18
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 洛谷P1034 矩形覆盖 2020-03-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash