「Luogu P2756」飞行员配对方案问题

发表于 |
字数统计: 681 | 阅读时长 ≈ 3

这个题是网络流24题中的第1题。
给一个二分图，求最大匹配以及匹配方案。

链接

Luogu P2756

题解

这个题目的模型是二分图最大匹配，有多个源点和汇点。所以可以增加一个超级源点和一个超级汇点。
超级源点1与2-(m+1)连流量为1的边；(m+2)-(n+1)与超级汇点n+2连流量为1的边；所给的边全部连流量为1的边。
最后，这个网络的最大流即为二分图的最大匹配。
对于每一条在二分图内的边，即它和它的反向边不连向源点和汇点，如果反向边有流量，就输出这条边连向的两个点。

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=1e5+51,inf=0x7fffffff;
struct Edge{
    ll to,prev,flow;
};
Edge ed[MAXN<<1];
ll l,nc,source,sink,tot=1,from,to,flow,maxFlow;
ll last[MAXN],depth[MAXN],inQueue[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline void addEdge(ll from,ll to,ll flow)
{
    ed[++tot].prev=last[from];
    ed[tot].to=to;
    ed[tot].flow=flow;
    last[from]=tot; 
}
inline ll Min(ll x,ll y)
{
    return x<y?x:y;
}
inline bool bfs()
{
    queue<ll>q;
    ll top,to;
    memset(depth,0x3f,sizeof(depth));
    depth[source]=0,q.push(source);
    while(!q.empty())
    {
        top=q.front();
        q.pop(),inQueue[top]=0;
        for(register int i=last[top];i;i=ed[i].prev)
        {
            to=ed[i].to;
            if(depth[to]>depth[top]+1&&ed[i].flow)
            {
                depth[to]=depth[top]+1;
                if(!inQueue[to])
                {
                    q.push(to),inQueue[to]=1;
                }
            }
        }
    }
    if(depth[sink]!=0x3f3f3f3f)
    {
        return 1;	
    } 
    return 0;
}
inline ll dfs(ll cur,ll flow)
{
    ll low;
    if(cur==sink)
    {
        return flow;
    }
    for(register int i=last[cur];i;i=ed[i].prev)
    {
        if(ed[i].flow&&depth[ed[i].to]==depth[cur]+1)
        {
            if(low=dfs(ed[i].to,Min(flow,ed[i].flow)))
            {
                ed[i].flow-=low,ed[i^1].flow+=low;
                return low;
            }
        }
    }
    return 0;
}
inline ll Dinic()
{
    ll flow;
    while(bfs())
    {
        while(flow=dfs(source,inf))
        {
            maxFlow+=flow;
        }
    }
    return maxFlow;
}
int main()
{
    l=read(),nc=read(),source=1,sink=nc+2;
    while(1)
    {
        from=read()+1,to=read()+1;
        if(!from||!to)
        {
            break;
        }
        addEdge(from,to,1),addEdge(to,from,0);
    }
    for(register int i=2;i<=l+1;i++)
    {
        addEdge(source,i,1),addEdge(i,source,0);
    }
    for(register int i=l+2;i<=nc+1;i++)
    {
        addEdge(i,sink,1),addEdge(sink,i,0);
    }
    if(Dinic()==0)
    {
        puts("No solution!");
    }
    else
    {
        printf("%d\n",maxFlow);
        for(register int i=2;i<=tot;i+=2)
        {
            if(ed[i].to!=source&&ed[i^1].to!=source&&ed[i].to!=sink&&ed[i^1].to!=sink)
            {
                if(ed[i^1].flow)
                {
                    printf("%d %d\n",ed[i^1].to-1,ed[i].to-1);
                }
            }
        }
    }
    
}