#include <bits/stdc++.h>
#define pr(p) printf("%d\n",p)
const int oo=2139063143;
const int N=500100;
const int mod=1000000007;
using namespace std;
typedef long long LL;
typedef double db;
inline void sc (int &x)
{
x=0; static int p; p=1; static char c; c=getchar();
while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
x*=p;
}
struct EDGE { int v,nx; }lb[N]; int tot=1,top[1010];
void add (int u,int v) { lb[++tot].v=v,lb[tot].nx=top[u],top[u]=tot; }
int match[1010];
bool vis[1010];
bool dfs (int u)
{
for (int kb=top[u]; kb!=-1; kb=lb[kb].nx)
{
int v=lb[kb].v;
if (!vis[v])
{
vis[v]=1;
if (!match[v]||dfs (match[v])) { match[v]=u; return 1; }
}
}
return 0;
}
int main()
{
//freopen (".in","r",stdin);
//freopen (".out","w",stdout);
memset (top,-1,sizeof (top));
int n,m,e,u,v,ans=0; sc(n),sc(m),sc(e);
for (int i=1; i<=e; i++)
{
sc(u),sc(v);
if (u<=n&&v<=m&&u>=1&&v>=1) add (u,v);
}
for (int i=1; i<=n; i++)
memset (vis,0,sizeof (vis)),ans+=dfs (i);
pr(ans);
return 0;
}
网络流。源点连左边点，左边连右边点，右边连汇点。
在二分图上选最少个数的点，使得所有的边都连到至少一个被选的点。
解法:$König定理：二分图中，最小点覆盖数等于最大匹配数。$
在二分图上选出最多的点，使得任意两个点之间没有连边。
解法:二分图中，最大独立集=点数-最小点覆盖=点数-最大匹配
给出一个有向无环图DAG，在上面选择最少的路径，使得每一个点都在一条路径中。
不相交路径最小覆盖。每一个点只能在一条路径中。
将每个点x拆为出点x+和入点x-，构成一个二分图。
如果原图有一条边<x,y>，那么就在二分图上连x+和y-。
原图节点数-最大匹配。
Luogu2764//格式要求
#include <bits/stdc++.h>
#define pr(p) printf("%d ",p)
const int oo=2139063143;
const int N=1010000;
const int mod=1000000007;
using namespace std;
typedef long long LL;
typedef double db;
inline void sc (int &x)
{
x=0; static int p; p=1; static char c; c=getchar();
while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
x*=p;
}
struct EDGE { int v,nx,w; }lb[N<<1]; int tot=1,top[N],cur[N];
void add (int u,int v,int w)
{
lb[++tot].v=v,lb[tot].w=w,lb[tot].nx=top[u],top[u]=tot;
lb[++tot].v=u,lb[tot].w=0,lb[tot].nx=top[v],top[v]=tot;
}
int s,t;
int d[N];
queue <int> q;
bool bfs ()
{
memset (d,0,sizeof (d));
memcpy (cur,top,sizeof (top));
q.push (s),d[s]=1;
bool ly=0;
while (q.size ())
{
int u=q.front (); q.pop ();
for (int kb=top[u]; kb!=-1; kb=lb[kb].nx)
{
int v=lb[kb].v,w=lb[kb].w;
if (w&&!d[v])
{
d[v]=d[u]+1;
q.push (v);
ly|=(v==t);
}
}
}
return ly;
}
int dinic (int u,int flow)
{
if (u==t) return flow;
int rest=flow;
for (; cur[u]!=-1&&rest; cur[u]=lb[cur[u]].nx)
{
int c=cur[u];
int v=lb[c].v,w=lb[c].w;
if (w&&d[v]==d[u]+1)
{
int k=dinic (v,min (rest,w));
if (!k) d[v]=0;
lb[c].w-=k;
lb[c^1].w+=k;
rest-=k;
if (!rest) break;
}
}
return flow-rest;
}
int fa[N],son[N];
int main()
{
//freopen (".in","r",stdin);
//freopen (".out","w",stdout);
memset (top,-1,sizeof (top));
int n,m; sc(n),sc(m);
s=n*2+1,t=s+1;
for (int i=1; i<=n; i++)
add (s,i,1),add (i+n,t,1);
for (int i=1; i<=m; i++)
{
int u,v; sc(u),sc(v);
add (u,v+n,1);
}
int ans=0,flow;
while (bfs ())
while ((flow=dinic (s,oo))) ans+=flow;
for (int u=1; u<=n; u++)
{
for (int kb=top[u]; kb!=-1; kb=lb[kb].nx)
{
int v=lb[kb].v,w=lb[kb^1].w;
if (v<=n||v==s||v==t) continue;
if (w) son[u]=v-n,fa[v-n]=u;
}
}
for (int i=1; i<=n; i++)
if (!fa[i])
{
int u=i;
pr(u);
while (son[u])
{
if (!son[son[u]]) { printf ("%d\n",son[u]); break; }
pr(son[u]),u=son[u];
}
}
printf ("%d",n-ans);
return 0;
}
可相交路径覆盖。
将图改造，若从a开始能到达的所有点的集合是S，就让点a直接连边到S中的每一个点。
可用Floyd传递闭包来算出新的图，然后按不相交路径覆盖计算。
偏序关系：定义符号≤和元素集S，称为偏序集，集合中有某些元素有关系A≤B。
满足数学中的性质。
若两元素可直接或间接通过≤联系起来，则它们是可比的，否则不可比。
链：S的一个子集，任意两元素可比。
反链：S的一个子集，任意两元素不可比。
最小链划分（不相交路径最小覆盖）=最长反链。
二分图每一条边有一个权值，要求在满足最大匹配的情况下，使得选出的边权值和最小（或最大）。
费用流。
二分图中所有点都被匹配了。
若一边的点少于另一边，设左边少，右边多。
那么若某匹配方案使少的那边的所有点都被匹配了，则称为S1到S2（啥？？）的完备匹配。
Hall定理：二分图存在完备匹配，当且仅当左边任意k个点至少和右边k个点相邻。
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：二分图匹配”