二分图匹配问题是一个简单的图论问题
一般来说使用匈牙利算法进行求解
但是由于正在学习网络流
希望通过网络流的方法来解决二分图最大匹配问题
听说Dinic方法求解二分图匹配的效率甚至比普通的匈牙利算法的时间复杂度还要低\( O(n\sqrt{m}) \)
所以就想写一发最大流来AC这个题目
首先先构图，源点为0，汇点为n+m+1
左边的编号从1到n
右边部分的编号从n+1到n+m
然后源点和左边连一条权值为1的边
右边与汇点连一条权值为1的边
然后跑一遍Dinic
网络最大流即为答案
注意这里的点数是n+m+2
边数是2*(n+m+e)
题目：洛谷P3386（模板题）
|
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 |
/************************************************************************* >>> Author: WindCry1 >>> Mail: lanceyu120@gmail.com >>> Website: https://windcry1.com >>> Date: 12/20/2019 7:09:38 PM *************************************************************************/ #include <cstring> #include <cmath> #include <cstdio> #include <cctype> #include <cstdlib> #include <ctime> #include <vector> #include <iostream> #include <string> #include <queue> #include <set> #include <map> #include <algorithm> #include <complex> #include <stack> #include <bitset> #include <iomanip> #include <list> #include <sstream> #include <fstream> #if __cplusplus >= 201103L #include <unordered_map> #include <unordered_set> #endif #define ll long long #define ull unsigned long long #define DEBUG(x) cout<<#x<<" : "<<x<<endl; #define lowbit(x) x&(-x) #define ls u<<1 #define rs u<<1|1 using namespace std; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const double clf = 1e-8; const int MMAX = 0x7fffffff; const int INF = 0x3f3f3f3f; const int mod = 1e9+7; const int dir[4][2]={-1,0,1,0,0,-1,0,1}; ostream& operator <<(ostream &out, pii &p){ return out<<p.first<<" "<<p.second; } istream& operator >>(istream &in, pii &p){ return in>>p.first>>p.second; } struct Edge{ int to,val,next; }edge[610000]; int head[2010],tot=1,n,m,e,ori,ed; bool book[2010]; int dep[2010]; inline void add_edge(int u,int v,int w){ edge[++tot].to=v; edge[tot].val=w; edge[tot].next=head[u]; head[u]=tot; } bool bfs(){ memset(book,0,sizeof book); dep[ori]=1;book[ori]=true; queue<int> q;q.push(ori); while(!q.empty()){ int t=q.front();q.pop(); for(int i=head[t];i;i=edge[i].next){ int v=edge[i].to,w=edge[i].val; if(w&&!book[v]){ dep[v]=dep[t]+1; book[v]=true; q.push(v); } } } return book[ed]; } int dfs(int x,int lim){ if(x==ed) return lim; for(int i=head[x];i;i=edge[i].next){ int v=edge[i].to,w=edge[i].val; if(dep[v]==dep[x]+1&&w){ int temp=dfs(v,min(w,lim)); if(temp){ edge[i].val-=temp; edge[i^1].val+=temp; return temp; } } } return 0; } int dinic(){ int res=0; while(bfs()){ int t=dfs(ori,INF); while(t){ res+=t; t=dfs(ori,INF); } } return res; } int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //ifstream cin("C:\\Users\\LENOVO\\Desktop\\in.txt"); //ofstream cout("C:\\Users\\LENOVO\\Desktop\\out.txt"); cin>>n>>m>>e; ed=n+m+1; while(e--){ int u,v;cin>>u>>v; if(u>n||v>m) continue; add_edge(u,v+n,1); add_edge(v+n,u,0); } for(int i=1;i<=n;i++) add_edge(ori,i,1),add_edge(i,ori,0); for(int i=n+1;i<=m+n;i++) add_edge(i,ed,1),add_edge(ed,i,0); cout<<dinic()<<endl; return 0; } |
2019-12-26 20:34 Author: WindCry1
0 条评论