洛谷 P2756 飞行员配对方案问题
程序员文章站
2022-06-05 16:10:42
全名:线性规划与网络流24题 按照题目难度顺序: 1.飞行员配对方案问题(求最大匹配数并且输出配对方案) 两种做法: 1)二分图匹配匈牙利算法,可以直接求出最大匹配数,并且数组中记录了最佳配对方案 2)最大流,超级源点S到A集合中每一个元素建边(容量为1),B集合中每一个点到汇点建边(容量为1),A ......
全名:线性规划与网络流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;
}
上一篇: Python的print的底层实现