c语言洛谷 P2756 飞行员配对方案问题

概述本文章向大家介绍c语言洛谷 P2756 飞行员配对方案问题，需要的朋友可以参考一下

全名:线性规划与网络流24题

按照题目难度顺序:

1.飞行员配对方案问题(求最大匹配数并且输出配对方案)

两种做法:

1)二分图匹配匈牙利算法,可以直接求出最大匹配数,并且数组中记录了最佳配对方案

2)最大流,超级源点S到A集合中每一个元素建边(容量为1),B集合中每一个点到汇点建边(容量为1),A集合中与B集合中可匹配的点之间建边(容量为1),跑最大流即可得到最大匹配数.

由于Dinic算法中被使用过的路流量会减少,而它的反向边流量会增加.

所以在最大匹配的时候,AB集合中两个点若配对,有 A -> B的边容量为0 (或B -> A的边容量为1).

二分图匈牙利版本：

#include

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,sizeof(match));

memset(to,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,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("%dn",hungry());

for(int i = 1;i <= m;++i)

if(to[i]) printf("%d %dn",i,to[i]);

return 0;

}

最大流dinic版本：

//最大流Dinic算法

//m为边数,n为点数

//复杂度O(m*n*n)

#include

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,sizeof(to));

memset(head,sizeof(head));

cnt = 0;

}

bool D_bfs(){

memset(dep,sizeof(dep));

memset(to,sizeof(to));

dep[s] = 1;

queue 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",&n);

s = 0,t = n+1;

for(int i = 1;i <= m;++i) ad(0,1);

for(int i = m+1;i <= n;++i) ad(i,n+1,1);

int u,v;

l = cnt;

while(scanf("%d%d",&v) && u != -1) ad(u,v,1);

r = cnt;

}

int main()

{

init();

getMap();

printf("%dn",Dinic());

for(int i = l;i < r;i += 2){

if(edge[i].w == 0){

printf("%d %dn",edge[i^1].to,edge[i].to);

}

}

return 0;

}

总结

以上是内存溢出为你收集整理的c语言洛谷 P2756 飞行员配对方案问题全部内容，希望文章能够帮你解决c语言洛谷 P2756 飞行员配对方案问题所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。