Preface

Bloggers are stupid , If there is any mistake , Welcome to point out the discussion in the comments section .

The maximum matching use of bipartite graphs \(Dinic\) Algorithm implementation , The time complexity is \(O(n\sqrt{e})\), among , \(n\) Is the number of left vertices in a bipartite graph , \(e\) Is the number of edges in a bipartite graph . If it's the Hungarian algorithm , The time complexity is \(O(nm)\) , \(m\) Is the number of right vertices in a bipartite graph , Not recommended .

Links to examples in the article .

König Theorem

Theorem content : The number of points covered by the smallest point of a bipartite graph be equal to The number of edges of a bipartite graph with maximum matching .

Construction method \(+\) Simple proof :

First, find the maximum matching in bipartite graph , It is recommended to use \(Dinic\) .

Starting from every unmatched point , Traversing along the direction of the unmatched edge , Mark the points traversed backward along the matching edge . Select the left point that has not been marked , The marked dot in the right dot , Then these points can form the minimum point cover of the bipartite graph .

The traversal code is implemented as follows :

void dfs(int now) {
vis[now] = true;
int SIZ = v[now].size();
for(int i = 0; i < SIZ; i++) {
int next = v[now][i].to;
if(vis[next] || !v[now][i].val)// The capacity of the positive side is 0 The description is the matching edge , The capacity of the opposite side is 0 The description is a non matching edge
continue;
dfs(next);
}
}

So it has the following properties :

  • If the point is a non matching point on the left , Then this point must be visited , Because this is the whole point \(dfs\) The starting point of the
  • If the point is a non matching point on the right , This point will not be accessed , If you reach this point from the unmatched point on the left , Then you can make this edge a matching edge , Then the matching number \(+1\) , Conflict with maximum match . If the matching point on the left reaches this point , So the path of this point is Left unmatched point Right matching point Left unmatched point Right matching point …… The matching point on the left Right mismatches , Obviously , The above path is Zengguang road , Conflict with maximum match . therefore , The mismatches on the right must not be accessed .
  • For a set of matching points , Or both are marked , Or they're not marked . Because the matching point on the left is traversed by the matching point on the right , There must be a couple .

With the above three properties , You can find : Select the unmarked points in the left point according to , The rule of the marked point in the right dot , The number of selected points must be the maximum number of matching edges . The unmatched point on the left must be accessed , You will not be elected , The mismatches on the right must not be accessed , You will not be elected . And the third nature determines , For a set of matching points , Will choose to have and only have one point . Therefore, the number of selected points is equal to the maximum number of matching edges .

Second, we need to solve a problem : Make sure these points cover all the edges . It can be divided into four categories :

  • The left part is the unmatched point , The right part is the unmatched point . Property two has been discussed , It's not possible , It does not satisfy the premise of maximum matching .
  • The left is the matching point , The right part is the unmatched point . The same is true for property two , The path is similar to , There's going to be an augmented road , Then the matching point on the left must not have been accessed , Must be chosen .
  • The left is the matching point , The right part is the matching point . One of the matching points must be selected .
  • The left part is the unmatched point , The right part is the matching point . This edge is unmatched , And the starting point is the unmatched dot on the left , So this point on the right must have been visited , Must be chosen .

Finally, make sure it's the smallest solution : There's only one point on each side , There is no waste .

Above , Certificate completion .

Title source :COCI 2019/2020 Contest #6 T4. Skandi

The main idea of the topic

Given a \(n\times m\) Matrix , The white dot is \(0\) , The black dots are \(1\) . The black dots can go down to the bottom , Turn white dots into blue dots , Until the black dot . Empathy , It can also be extended to the right . How many times can the whole matrix be expanded to the point where there is no white , And print out where each expansion started , And print out the expansion direction . The first line and the first column must be black dots .

Ideas

A modeling problem .

There are only two ways to turn a white dot into a blue dot , From the black dot above or to the left , And it only needs one point to expand . We can consider the minimum point coverage problem .

Because for a black dot , It can expand to the right or down . So it has two identities , That is to say, a point has two numbers . A number is the order in which the entire matrix is pulled into a chain , The other number is the previous number \(+n\times m\) , So there's no conflict . Get the numbered function :

int GetHash(int i, int j) {
return (i - 1) * m + j;
}

So it's not hard to find a white dot , Associated with it is a number \(\leqslant n\times m\) The point of , And a number \(>n\times m\) The point of . Connect these two points , It's a bipartite graph .

The problem is to find the minimum point cover of this graph . Use \(Dinic\) , According to the above \(König\) Theorem construction can be .

The number of sides is the number of white dots , The left dot is the number of black dots , Then the time complexity is \(O(nm\sqrt{nm})\) , namely \(O(n^{\frac{3}{2}}m^{\frac{3}{2}})\) , Topic \(n\) , \(m\) All less than \(500\) , Probably in \(1s\) Find out the answer in .

C++ Code

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f
const int MAXN = 1e6 + 5;
const int MAXM = 5e2 + 5;
struct Node {
int to, val, rev;// In turn : The next point , Edge capacity , The number of the opposite side
Node() {}
Node(int T, int V, int R) {
to = T;
val = V;
rev = R;
}
};
vector<Node> v[MAXN];// use vector The habit of saving pictures ...
int dn[MAXN], rt[MAXN];// Preprocessing white dots can be extended from the right two dots
queue<int> q;
int de[MAXN], be[MAXN];
int twin[MAXN];
bool vis[MAXN];
int n, m, s, t;
int arr[MAXM][MAXM];
bool bfs() {// Layer the residual network
bool flag = 0;
memset(de, 0, sizeof(de));
while(!q.empty())
q.pop();
q.push(s);
de[s] = 1; be[s] = 0;
while(!q.empty()) {
int now = q.front();
q.pop();
int SIZ = v[now].size();
for(int i = 0; i < SIZ; i++) {
int next = v[now][i].to;
if(v[now][i].val && !de[next]) {
q.push(next);
be[next] = 0;
de[next] = de[now] + 1;
if(next == t)
flag = 1;
}
}
}
return flag;
}
int dfs(int now, int flow) {// Along the Zengguang road
if(now == t || !flow)
return flow;
int i, surp = flow;
int SIZ = v[now].size();
for(i = be[now]; i < SIZ && surp; i++) {
be[now] = i;
int next = v[now][i].to;
if(v[now][i].val && de[next] == de[now] + 1) {
int maxnow = dfs(next, min(surp, v[now][i].val));
if(!maxnow)
de[next] = 0;
v[now][i].val -= maxnow;
v[next][v[now][i].rev].val += maxnow;
surp -= maxnow;
}
}
return flow - surp;
}
int Dinic() {// Network maximum flow , It can also be used for bipartite graph matching
int res = 0;
int flow = 0;
while(bfs())
while(flow = dfs(s, INF))
res += flow;
return res;
}
int GetHash(int i, int j) {// Get the number of the point
return (i - 1) * m + j;
}
void Down(int now, int i, int j) {// The black dot extends down , Each white dot can be traversed up to one time at most
if(i != now)
dn[GetHash(now, j)] = GetHash(i, j);
if(arr[now + 1][j] == 2)
Down(now + 1, i, j);
}
void Right(int now, int i, int j) { // The black dot extends to the right , Each white dot can be traversed up to one time at most
if(j != now)
rt[GetHash(i, now)] = GetHash(i, j) + n * m;
if(arr[i][now + 1] == 2)
Right(now + 1, i, j);
}
void GetMin(int now) {//dfs Find the way of construction
vis[now] = true;
int SIZ = v[now].size();
for(int i = 0; i < SIZ; i++) {
int next = v[now][i].to;
if(vis[next] || !v[now][i].val)
continue;
GetMin(next);
}
}
int main() {
scanf("%d %d", &n, &m);
s = 0; t = 2 * n * m + 1;// Source and sink initialization
char ch;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> ch;
if(ch == '1')
arr[i][j] = 1;
else
arr[i][j] = 2;
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(i == 1 && j == 1)
continue;
if(arr[i][j] == 1) {// Right or down , A white spot will be visited 2 Time
Down(i, i, j);
Right(j, i, j);
}
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
if(arr[i][j] == 1) {// Source to left , The meeting point to the right is connected to the side
int now = GetHash(i, j);
int idnow = v[now].size();
int ids = v[s].size();
v[s].push_back(Node(now, 1, idnow));
v[now].push_back(Node(s, 0, ids));
now = GetHash(i, j) + n * m;
idnow = v[now].size();
int idt = v[t].size();
v[now].push_back(Node(t, 1, idt));
v[t].push_back(Node(now, 0, idnow));
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(i == 1 && j == 1)
continue;
if(arr[i][j] == 1)
continue;
int A = dn[GetHash(i, j)];// From the left to the right
int B = rt[GetHash(i, j)];
int idA = v[A].size();
int idB = v[B].size();
v[A].push_back(Node(B, 1, idB));
v[B].push_back(Node(A, 0, idA));
}
}
printf("%d\n", Dinic());
GetMin(s);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(arr[i][j] == 2)
continue;
if(!vis[GetHash(i, j)])// Print answers
printf("%d %d DOLJE\n", i, j);
if(vis[GetHash(i, j) + n * m])
printf("%d %d DESNO\n", i, j);
}
}
return 0;
}

The construction scheme of minimum point cover of bipartite graph +König More articles on theorem proving

  1. UVA1194 Machine Schedule[ Minimum vertex covering of bipartite graph ]

    Title Translation There are two machines A,B There were n,m Patterns . Now there is k A mission . For each task i , Given two integers $ a_i\( and \) b_i$, If the task is in A On the implementation , You need to set the mode to \(a_i\): ...

  2. POJ2226 Muddy Fields( Minimum vertex covering set of bipartite graphs )

    For Zhang R×C The map of , On the map * It means mud .. Pasture , Ask at least a few pieces wide 1 Any long board can cover all the mud , The boards can overlap, but they can't cover the grass . Put all rows and columns in continuous mud ( It can be covered with a board ) As point and row and column continuous mud respectively ...

  3. POJ1325 Machine Schedule( Minimum vertex covering set of bipartite graphs )

    Minimum point covering set is to select the least point set in a digraph , Make it cover all the edges . Minimum vertex covering set of bipartite graphs = Maximum matching of bipartite graph ( The largest edge independent set of bipartite graphs ) This question A Mechanical n There are two models as X The point of the Ministry ,B Mechanical m There are two models as Y The point of the Ministry : Every mission is ...

  4. hihoCoder #1127: Minimum vertex covering and maximum independent set of bipartite graphs

    The main idea of the topic : Find the minimum point cover and maximum independent set of bipartite graph . Topic analysis : If you select a point , So all the edges connected to this point are covered , The minimum set of points that makes all edges covered is called minimum point covering , It's equal to the maximum match : The largest set of points with no edge between any two points is called ...

  5. [POJ] 2226 Muddy Fields( Minimum vertex covering of bipartite graph )

    Title address :http://poj.org/problem?id=2226 The key to the problem of bipartite graph is to construct a graph . because “*” There are only two ways to cover the area with wood : Horizontal or vertical , So use this way to dichotomy . First of all, in rows , Work out each &q ...

  6. Bipartite graph Minimum point coverage poj 3041

    Topic link :Asteroids - POJ 3041 - Virtual Judge  https://vjudge.net/problem/POJ-3041 Enter one on the first line n And a m It means that n*n The grid of ...

  7. HihoCoder1127 Bipartite graph three &#183; Minimum vertex covering and maximum independent set of bipartite graphs

    Bipartite graph three · Minimum vertex covering and maximum independent set of bipartite graphs The time limit :10000ms Single point time limit :1000ms Memory limit :256MB describe It's been a long time since the last blind date , Everyone seems to have met . But blind date doesn't mean ...

  8. hdu 2236( Minimum vertex covering of bipartite graph + Two points )

    Untitled II Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submis ...

  9. The 7th Sichuan D Vertex Cover( Minimum vertex covering of bipartite graph , Binary matching template )

    Vertex Cover frog has a graph with nn vertices v(1),v(2),…,v(n)v(1),v(2),…,v(n) and mm edges (v(a1), ...

  10. hihoCoder #1127 : Bipartite graph 2 &#183; Minimum vertex covering and maximum independent set of bipartite graphs

    #1127 : Bipartite graph 2 · Minimum vertex covering and maximum independent set of bipartite graphs Time Limit:10000ms Case Time Limit:1000ms Memory Limit:256MB describe After arranging a blind date last time ...

Random recommendation

  1. SVN Update error

    Put the server SVN File update to local is the following error It has been indicated in the error report that it can pass clean up To clean up , If directly executed release lock, It won't solve the problem . reason : There are expired working copies in the local project terms of settlement : Choose the article ...

  2. js Seamless connection of pictures

    design sketch 1. First look at html and css Code <style> *{padding:0;margin:0;} #div1{margin:100px auto;background:red;wi ...

  3. Power-BI Adaptive settings for common functions of reports

    Power-BI Reports can be browsed across platforms , And adapt to a variety of screen sizes . stay Power-BI Under the development interface of , There are several properties used to set the presentation mode of the report on different screens , To achieve a better user experience . 1.PC Layout : Set the report in PC The cloth on the plane ...

  4. gentoo Next grub File editing

    After compiling the kernel , Configure the network , Good configuration fstab Documents, etc. , The last crucial document belongs to grub The file , The final decision is to configure the file successfully gentoo Whether it was successfully installed , First of all, of course emerge grub 了 , You can match it now ...

  5. [osgEarth]osgEarth

    Reference resources :http://bbs.osgchina.org/forum.php?mod=viewthread&tid=5484&extra=page%3D1&_dsign=70b15 ...

  6. Learn front end development from scratch — 3、CSS The box model

    *  css The box model is css Cornerstone , Every html Labels can be seen as a box model . css The box model is made up of content (content), Fill in or fill in (padding), Frame (border), Margin (margin) Four-part composition ...

  7. localStorage and sessionStorage difference ( Including the definition of homology )

    localStorage and sessionStorage The same is used to store client temporary information objects . They can only store objects of string type ( Although the specification can store other native types of objects , But so far no browser has implemented it ) ...

  8. webpack What is it?

    1, Packaging tools Module packaging 2. Front end engineer , Essential tools webpack effect 1. pack ( Multiple files , Package it into a file ) 2. conversion (less,sass,ts) Need the core technology loader 3 Optimize (SPA More and more ...

  9. html Commonly used meat head

    <!-- Font encoding --> <meta charset="utf-8" /> <!-- keyword --> <meta name=" ...

  10. OO The third blog

    The history of standardized design In the early development of computers , There is no systematic approach to software development , Often only source code and no software specification and other documents , Therefore, the universality of software in this period is very limited . Then came. 20 century 60 years , Software began to be widely used , Software ...