摸鱼第一,干活第二

It's time for BOOM!(ノ≧∀≦)ノ

【网络流24题】①飞行员配对方案问题

真真正正为了学习开的系列,顺便把任务清单的最大流写了。

本系列需要少量的网络流基础,因为不会介绍一些网络流相关的术语。

不过用着百度一边看基本上也不会有什么障碍。


网络流24题之第一题——飞行员配对方案问题

原题见洛谷P2756


题解

非常非常非常基础的二分图匹配问题,但是如果不用网络流来解决的话标题就应该改成匈牙利算法了。

对于网络流这种东西,流量算法千千万,最重要的是建成网络流模型。

这里根据题目信息想都不用想,不涉及费用问题,直接跑裸最大流。不过题目要求我们输出方案,所以只要成功增广节点时,记录后继节点编号就行了。

简单谈谈为什么可以用网络流(其实匈牙利算法就是一种网络流),先让我们看一下流量图:

所有的边容量都为1。

《【网络流24题】①飞行员配对方案问题》

题目要求我们找到最大匹配,这个网络中就是要我们找到用最少的路线数量连接源点S与汇点T,使S、T之间无路可走,这样在源点所加的流量就是最大流。这就相当于把整个图割成几部分,使S、T不在同一部分内,因而最大流又被称作最小割

这张图太水了一点,一眼就能看出应该怎么选:

《【网络流24题】①飞行员配对方案问题》

假如题目要求我们匹配A、B,那么从中间红线连接就可以看出最多可以匹配那些了(答案其实并不唯一,所以有SPJ),所以网络流可以完成这种题目。

对于怎么建模,除了根据要求在点之间连边之外,我们还要给一边全部连接到源点S上,另一边全部连接到汇点T上,边容量设为1(记得建0容量反边),然后就可以快乐地跑最大流了。


流量算法——ISAP

洛谷上有大佬讲了:点击这里跳转

(其实网络流题目流量算法背板就好了,因为重要的是怎么建模,然后把算法一套)

时间复杂度:\(O(N^{2}M)\)(N:点数,M:边数)


代码

这是非常香港的代码。ISAP快真的快(HLPP不敢说,虽然常数大,但是这道题应该会比ISAP快)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define il inline
#define inf 0x3F3F3F3F

//快速读入
char gtc();
int rdI();

//链式前向星
struct nd{
    int to,cp,nx;
} edge[5105];
int top;
int head[105];
void addEdge(int,int,int);

//队列
int h,t;
int q[205];
void resetQueue();
void pushQueue(int);
int popQueue();

//最大流
int mxf;
int dep[105],gap[105],cur[105],pst[105];
void bfs();
int dfs(int,int);
void ISAP();

int M,N,I,J;

int main(){
    M=rdI();N=rdI();
    I=rdI();J=rdI();
    while(I!=-1){
        addEdge(I,J,1);
        I=rdI();J=rdI();
    }
    for(int i=1;i<=M;++i)
        addEdge(0,i,1);
    for(int i=M+1;i<=N;++i)
        addEdge(i,N+1,1);
    ISAP();
    if(mxf==0){
        printf("No Solution!");
        return 0;
    }
    printf("%d\n",mxf);
    for(int i=1;i<=M;++i)
        if(pst[i])
            printf("%d %d\n",i,pst[i]);
    return 0;
}

//划分深度&统计同深度节点数量
il void bfs(){
    int u,v;
    memset(dep,-1,sizeof dep);
    memset(gap,0,sizeof gap);
    //从汇点出发,反着来跑
    dep[N+1]=0;
    gap[0]=1;
    resetQueue();
    pushQueue(N+1);
    while(h!=t){//很普通的图形广度遍历
        u=popQueue();
        for(int i=head[u];i;i=edge[i].nx){
            v=edge[i].to;
            if(dep[v]!=-1)//不打扰已经遍历过的点
                continue;
            dep[v]=dep[u]+1;//划分深度
            ++gap[dep[v]];//统计数量
            pushQueue(v);
        }
    }
}
//找增广路
int dfs(int u,int f){
    if(u==N+1)//到汇点了
        return mxf+=f,f;//更新最大流&最大可行路线流量返回上一层
    int v,used=0;
    for(int i=cur[u];i;i=edge[i].nx){
        cur[u]=i;//还是弧优化
        v=edge[i].to;
        if(edge[i].cp&&dep[v]+1==dep[u]){//有空余容量&没有断层
            int mn=dfs(v,min(edge[i].cp,f-used));//管道灌水
            if(mn){//灌水成功了
                pst[u]=v;//记录后继
                //调整正反流量
                edge[i].cp-=mn;
                edge[i^1].cp+=mn;
                used+=mn;//统计总共成功灌水量
            }
            if(used==f)//成功灌水量与上一层留过来的流量相等了,也就是没水供你灌了
                return used;//最大可行路线流量返回上一层
        }
    }
    --gap[dep[u]];
    if(!gap[dep[u]])//出现断层意味着已经无路可走,可以直接退出ISAP了
        dep[0]=N+1;
    //重新计算深度&统计同深度节点数量
    ++dep[u];
    ++gap[dep[u]];
    return used;//最大可行路线流量返回上一层
}
//ISAP主程序
il void ISAP(){
    bfs();
    while(dep[0]<N){
        memcpy(cur,head,sizeof cur);//弧优化
        dfs(0,inf);
    }
}
//重置队列
il void resetQueue(){
    h=t=0;
}
//入队
il void pushQueue(int _x){
    ++t<405?(q[t]=_x):(q[t=0]=_x);
}
//出队
il int popQueue(){
    return ++h<405?q[h]:q[h=0];
}
//插边
il void addEdge(int _x,int _y,int _z){
    edge[top]=(nd){_y,_z,head[_x]};
    head[_x]=top;
    //不要忘了插反流边
    edge[++top]=(nd){_x,0,head[_y]};
    head[_y]=top++;
}
//代替getchar()
il char gtc(){
    static char buff[0xFFFFF],*p1=buff,*p2=buff;
    return p1==p2&&(p2=(p1=buff)+fread(buff,1,0xFFFFF,stdin),p1==p2)?EOF:*p1++;
}
//快速读入整数
il int rdI(){
    int f=1,t=0;
    char c=gtc();
    while((c<'0'||c>'9')&&c!='-')
        c=gtc();
    if(c=='-'){
        f=-1;
        c=gtc();
    }
    while(c>='0'&&c<='9'){
        t=t*10+c-'0';
        c=gtc();
    }
    return f*t;
}

【END】

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code