二分图匹配

https://www.luogu.org/problemnew/show/P3386

最快的方法 dinic：

O(n*sqrt(m))

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <ctime>
  5 #include <cstring>
  6 #include <string>
  7 #include <map>
  8 #include <set>
  9 #include <list>
 10 #include <queue>
 11 #include <stack>
 12 #include <vector>
 13 #include <bitset>
 14 #include <algorithm>
 15 #include <iostream>
 16 using namespace std;
 17 #define ll long long
 18 const int maxn=2e3+10;///两边的点，加上新增的起点和终点，注意！！！
 19 const int inf=1e9;
 20 
 21 struct node
 22 {
 23     int d,len;
 24     node *next,*opp;
 25 }*e[maxn],*pre[maxn];
 26 
 27 int s,t,dep[maxn],q[maxn];
 28 bool vis[maxn];
 29 
 30 void add_edge(int x,int y,int len)
 31 {
 32     node *p1=(node*) malloc (sizeof(node));
 33     node *p2=(node*) malloc (sizeof(node));
 34 
 35     p1->d=y;
 36     p1->len=len;
 37     p1->next=e[x];
 38     p1->opp=p2;
 39     e[x]=p1;
 40 
 41     p2->d=x;///注意
 42     p2->len=0;///注意
 43     p2->next=e[y];
 44     p2->opp=p1;;
 45     e[y]=p2;
 46 }
 47 
 48 bool bfs()
 49 {
 50     int head=0,tail=1,d,dd;
 51     node *p;
 52     memset(vis,0,sizeof(vis));
 53     q[1]=s;
 54     dep[s]=0;
 55     vis[s]=1;
 56     while (head<tail)
 57     {
 58         head++;
 59         d=q[head];
 60         p=e[d];
 61         while (p)
 62         {
 63             dd=p->d;
 64             if (p->len>0 && !vis[dd])
 65             {
 66                 vis[dd]=1;
 67                 tail++;
 68                 q[tail]=dd;
 69                 dep[dd]=dep[d]+1;
 70             }
 71             p=p->next;
 72         }
 73     }
 74     if (vis[t])
 75         return 1;
 76     return 0;
 77 }
 78 
 79 int dfs(int d,int add)
 80 {
 81     if (!add || d==t)
 82         return add;
 83     int totf=0,f,dd;
 84     node *p=e[d];
 85     while (p)
 86     {
 87         dd=p->d;
 88         if (dep[dd]==dep[d]+1 && (f=dfs(dd,min(add,p->len)))>0)///注意
 89         {
 90             totf+=f;
 91             add-=f;///注意
 92             p->len-=f;
 93             p->opp->len+=f;
 94             if (!f)
 95                 break;
 96         }
 97         p=p->next;
 98     }
 99     return totf;
100 }
101 
102 int main()
103 {
104     int n,m,e,x,y,i,sum=0;
105     scanf("%d%d%d",&n,&m,&e);
106     s=0,t=n+m+1;
107     for (i=1;i<=n;i++)
108         add_edge(s,i,1);
109     for (i=n+1;i<=n+m;i++)
110         add_edge(i,t,1);
111     for (i=1;i<=e;i++)
112     {
113         scanf("%d%d",&x,&y);
114         if (x>n || y>m)
115             continue;
116         add_edge(x,y+n,1);
117     }
118     while (bfs())
119         sum+=dfs(s,inf);
120     printf("%d",sum);
121     return 0;
122 }

vis:是否在配对中使用过

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <time.h>
 6 #include <string>
 7 #include <set>
 8 #include <map>
 9 #include <list>
10 #include <stack>
11 #include <queue>
12 #include <vector>
13 #include <bitset>
14 #include <ext/rope>
15 #include <algorithm>
16 #include <iostream>
17 using namespace std;
18 #define ll long long
19 #define minv 1e-6
20 #define inf 1e9
21 #define pi 3.1415926536
22 #define duishu  2.7182818284
23 const ll mod=1e9+7;//998244353
24 const int maxn=1e3+10;
25 
26 struct node
27 {
28     int d;
29     node *next;
30 }*e[maxn];
31 
32 bool vis[maxn]={0};
33 int conx[maxn],cony[maxn]={0};
34 
35 inline void read(int &x)
36 {
37     x=0;
38     char ch=getchar();
39 //    bool f;
40 //    while (ch<'0' || ch>'9')
41 //        f|=ch=='-',ch=getchar();
42     while (ch<'0' || ch>'9')    //no negative number
43         ch=getchar();
44     while (ch>='0' && ch<='9')
45         x=x*10+ch-'0',ch=getchar();
46 }
47 
48 bool dfs(int x)
49 {
50     node *p=e[x];
51     int y;
52     while (p)
53     {
54         y=p->d;
55         if (!vis[y])
56         {
57             vis[y]=1;
58             if (cony[y]==0 || dfs(cony[y]))
59             {
60                 conx[x]=y;
61                 cony[y]=x;
62                 return 1;
63             }
64         }
65         p=p->next;
66     }
67     return 0;
68 }
69 
70 int main()
71 {
72     node *p;
73     int n,m,E,x,y,i,sum=0;
74     scanf("%d%d%d",&n,&m,&E);
75     for (i=1;i<=n;i++)
76         e[i]=NULL;
77     while (E--)
78     {
79         read(x),read(y);
80         if (x<=n && y<=m)
81         {
82             p=(node*) malloc (sizeof(node));
83             p->d=y;
84             p->next=e[x];
85             e[x]=p;
86         }
87     }
88     for (i=1;i<=n;i++)
89     {
90         memset(vis,0,sizeof(vis));
91         sum+=dfs(i);
92     }
93     cout<<sum;
94     return 0;
95 }

题目：

https://www.luogu.org/problemnew/show/P2319

[HNOI2006]超级英雄

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <time.h>
  6 #include <string>
  7 #include <set>
  8 #include <map>
  9 #include <list>
 10 #include <stack>
 11 #include <queue>
 12 #include <vector>
 13 #include <bitset>
 14 #include <ext/rope>
 15 #include <algorithm>
 16 #include <iostream>
 17 using namespace std;
 18 #define ll long long
 19 #define minv 1e-6
 20 #define inf 1e9
 21 #define pi 3.1415926536
 22 #define duishu  2.7182818284
 23 const ll mod=1e9+7;//998244353
 24 const int maxn=1e3+10;
 25 
 26 struct node
 27 {
 28     int d;
 29     node *next;
 30 }*e[maxn];
 31 
 32 int conx[maxn],cony[maxn];
 33 bool vis[maxn];
 34 
 35 bool dfs(int x)
 36 {
 37     node *p=e[x];
 38     int y;
 39     while (p)
 40     {
 41         y=p->d;
 42         if (!vis[y])
 43         {
 44             vis[y]=1;
 45             if (cony[y]==-1 || dfs(cony[y]))
 46             {
 47                 conx[x]=y;
 48                 cony[y]=x;
 49                 return 1;
 50             }
 51         }
 52         p=p->next;
 53     }
 54     return 0;
 55 }
 56 
 57 int main()
 58 {
 59     node *p;
 60     int n,m,x,y,i,l,r,M,sum;
 61     scanf("%d%d",&n,&m);
 62     for (i=1;i<=m;i++)
 63     {
 64         scanf("%d%d",&x,&y);
 65         p=(node*) malloc (sizeof(node));
 66         p->d=x;
 67         p->next=e[i];
 68         e[i]=p;
 69 
 70         if (x==y)
 71             continue;
 72         p=(node*) malloc (sizeof(node));
 73         p->d=y;
 74         p->next=e[i];
 75         e[i]=p;
 76     }
 77 
 78     l=1,r=n;
 79     while (l<=r)
 80     {
 81         M=(l+r)>>1;
 82         for (i=0;i<n;i++)
 83             cony[i]=-1;
 84         sum=0;
 85         for (i=1;i<=M;i++)
 86         {
 87             memset(vis,0,sizeof(vis));
 88             sum+=dfs(i);
 89         }
 90         if (sum==M)
 91             l=M+1;
 92         else
 93             r=M-1;
 94     }
 95 
 96     printf("%d
",r);
 97     for (i=1;i<=r;i++)
 98         printf("%d
",conx[i]);
 99     return 0;
100 }