洛谷 P3386 【模板】二分图匹配 Dinic版

题目背景

二分图

题目描述

给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数

输入输出格式

输入格式:

第一行,n,m,e

第二至e+1行,每行两个正整数u,v,表示u,v有一条连边

输出格式:

共一行,二分图最大匹配

输入输出样例

输入样例#1:

1 1 1
1 1

输出样例#1:

1

说明

n,m \leq 1000n,m≤1000, 1 \leq u \leq n1≤u≤n, 1 \leq v \leq m1≤v≤m

因为数据有坑,可能会遇到 v>mv>m 的情况。请把 v>mv>m 的数据自觉过滤掉。

算法:二分图匹配

建一个超级源点S

建一个超级汇点T

连n条S到1-n的边

连m条n+1-n+1+m到T的边

所有边的权值都是1

跑最大流

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 const int MAXN=3*1e6;
 8 const int INF=0x7ffff;
 9 inline int read()
10 {
11     char c=getchar();int flag=1,x=0;
12     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
13     while(c>='0'&&c<='9')     x=x*10+c-48,c=getchar();return x*flag;
14 }
15 struct node
16 {
17     int u,v,f,nxt;
18 }edge[MAXN];
19 int head[MAXN];
20 int num=0;
21 inline void add_edge(int x,int y,int z)
22 {
23     edge[num].u=x;
24     edge[num].v=y;
25     edge[num].f=z;
26     edge[num].nxt=head[x];
27     head[x]=num++;
28 }
29 int n,m,e;
30 int S,T;
31 int deep[MAXN],cur[MAXN];
32 inline bool BFS()
33 {
34     memset(deep,0,sizeof(deep));
35     deep[S]=1;
36     queue<int>q;
37     q.push(S);
38     while(q.size()!=0)
39     {
40         int p=q.front();q.pop();
41         for(int i=head[p];i!=-1;i=edge[i].nxt)
42             if(deep[edge[i].v]==0&&edge[i].f)
43                 deep[edge[i].v]=deep[p]+1,q.push(edge[i].v);
44     }
45     return deep[T];
46 }
47 int DFS(int now,int nowflow)
48 {
49     if(nowflow<=0||now==T)    return nowflow;
50     int totflow=0;
51     for(int &i=cur[now];i!=-1;i=edge[i].nxt)
52     {
53         if(deep[edge[i].v]==deep[now]+1&&edge[i].f)
54         {
55             int canflow=DFS(edge[i].v,min(edge[i].f,nowflow));
56             totflow+=canflow;
57             nowflow-=canflow;
58             edge[i].f-=canflow;
59             edge[i^1].f+=canflow;    
60             if(nowflow<=0)    break;
61         }
62     }
63     return totflow;
64 }
65 int ans=0;
66 inline void Dinic()
67 {
68     while(BFS())
69     {
70         memcpy(cur,head,sizeof(head));
71         ans+=DFS(S,INF);
72     }
73         
74 }
75 int main()
76 {
77     memset(head,-1,sizeof(head));
78     n=read();m=read();e=read();
79     for(int i=1;i<=e;i++)
80     {
81         int x=read(),y=read();
82         add_edge(x,y+n,1);
83         add_edge(y+n,x,0);
84     }
85     S=0,T=INF;
86     for(int i=1;i<=n;i++)
87         add_edge(S,i,1),add_edge(i,S,0);
88     for(int i=1;i<=m;i++)
89         add_edge(i+n,T,1),add_edge(T,i+n,0);
90     Dinic();
91     printf("%d",ans);
92     return 0;
93 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

Codeforces 626C Block Towers(二分)

C. Block Towers time limit per test:2 seconds memory limit per test:256 megabyte...

28450
来自专栏云霄雨霁

数据压缩----霍夫曼树和霍夫曼压缩

21400
来自专栏小樱的经验随笔

华中农业大学第五届程序设计大赛网络同步赛题解

A.Little Red Riding Hood ? B.Choosy in Food •F[i]:从第I个点到终点的期望步数 •F[i] = (F[i +...

36770
来自专栏mathor

TRIE(3)

 搜索引擎现在一般都有关键词提示或者说是补全功能。就是当你在搜索框里输入一个关键词s时,搜索引擎会自动提示你一些频率比较高,同时前缀是s的关键词  这道...

11420
来自专栏Bingo的深度学习杂货店

Q107 Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' va...

27580
来自专栏数据结构与算法

P3379 【模板】最近公共祖先(LCA)

题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 输入输出格式 输入格式: 第一行包含三个正整数N、M、S,分别表示树的结点个数...

45660
来自专栏蜉蝣禅修之道

LeetCode之Binary Tree Maximum Path Sum

13640
来自专栏工科狗和生物喵

【编程能力不行?那就写啊!】二叉索引树

本文直接借鉴下面的博客进行补充: 区间信息的维护与查询(一)——二叉索引树(Fenwick树、树状数组)

15460
来自专栏杨熹的专栏

【LEETCODE】模拟面试-46. Permutations

notice: if ( curList.contains(arr[i]) ){ continue; ...

389120
来自专栏小樱的经验随笔

51 Nod 1005 大数加法【Java大数乱搞,python大数乱搞】

1005 大数加法 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 给出2个大整数A,B,计算A+B的结果。 Input 第1行:...

41190

扫码关注云+社区

领取腾讯云代金券