搞完了网络流图，搞完了一般图，最后应该是二分图了（在本沙茶知道的图的范围内）
二分图的边有些特别，边<a, b>并不是表示从a到b的边，而是从X方点a（简记为X
a）到Y方点b（简记为Y
b）的边。在二分图中，边其实是无向的，但由于大多数引用的时候都是X方点引用Y方点，所以可以把边看成有向的（如果实在要逆向引用的话，加一条逆向边吧囧……）
边类型定义（和一般图完全一致。这里是不带权的，如果像KM算法里面有带权边，加一个len域即可）：
struct edge {
int a, b, pre, next;
} ed[MAXM];
关键是在初始化表头的时候，设图中有NX个X方点和NY个Y方点，则单点链表数其实只有NX。故只需弄NX个表头即可：
void init_d()
{
re(i, nx) ed[i].a = ed[i].pre = ed[i].next = i;
if (nx % 2) m = nx + 1; else m = nx;
}
然后是加边，和一般图完全一致：
void add_edge(int a, int b)
{
ed[m].a = a; ed[m].b = b; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
}
差不多就搞完了。下面是用Dancing Link边表实现的Hungary算法的深度优先遍历部分：
bool dfs(int x)
{
vst[x] = 1;
int y, x1;
for (int p=ed[x].next; p != x; p=ed[p].next) {
y = ed[p].b; x1 = xz[y];
if (x1 == -1 || !vst[x1] && dfs(x1)) {
xz[y] = x; return 1;
}
}
return 0;
}
这里xz[y]指的是y所匹配的X方点编号（若y是未盖点则xz[y]=-1），vst[x]是X方点x是否被访问的标志，在每次遍历前，vst都要全部清零。
【应用实例】
PKU1087题意很难懂，其实就是：房间里有N个插座，每个插座都有一个型号（没有两个插座的型号相同），现在要把M个用电器插到这N个插座里，每个用电器有一个默认型号，表示该用电器只能插到其默认型号的插座里（有可能有的用电器的默认型号不与房间里的任意一个插座对应，如样例中的X型号）。有K种适配器（每种适配器可以用无限次），每一种适配器都有两个参数S1和S2，表示该种适配器使用一次可以将某个默认型号为S1的用电器的默认型号改为S2（同一个用电器可以被多次改变默认型号）。问在使用了若干次适配器后，最少有多少个用电器插不到插座里？
首先将每种型号作为一个点，若某种适配器的两个参数分别为S1和S2则连边<S1, S2>，对这个有向图求传递闭包。然后再建一个二分图，X方点表示用电器，Y方点表示插座，若X
i的初始默认型号在一开始建的有向图中可以到达Y
j的型号（用传递闭包直接得到），则连边(X
i, Y
j)。对这个二分图求最大匹配，则(M - 最大匹配值)就是结果。
代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
const int MAXN = 500, MAXM = 250500, MAXLEN = 50, INF = ~0U >> 2;
struct edge {
int a, b, pre, next;
} ed[MAXM];
int n, nx, ny, m, xt[MAXN], yt[MAXN], xz[MAXN], res = 0;
bool f[MAXN][MAXN], vst[MAXN];
string nm[MAXN];
void init()
{
string s1, s2;
char s01[MAXLEN], s02[MAXLEN], ch;
scanf("%d", &ny); ch = getchar();
re(i, ny) {gets(s01); nm[i] = s01; yt[i] = i;} n = ny;
scanf("%d", &nx); ch = getchar();
re(i, nx) {
scanf("%s %s", s01, s02); ch = getchar(); xt[i] = n;
re(j, n) if (nm[j] == s02) {xt[i] = j; break;}
if (xt[i] == n) nm[n++] = s02;
}
int z, t1, t2;
scanf("%d", &z); ch = getchar();
re(i, z) {
scanf("%s %s", s01, s02); ch = getchar();
t1 = n; re(j, n) if (nm[j] == s01) {t1 = j; break;}
if (t1 == n) nm[n++] = s01;
t2 = n; re(j, n) if (nm[j] == s02) {t2 = j; break;}
if (t2 == n) nm[n++] = s02;
f[t1][t2] = 1;
}
re(i, n) f[i][i] = 1;
}
void add_edge(int a, int b)
{
ed[m].a = a; ed[m].b = b; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
}
void prepare()
{
re(k, n) re(i, n) re(j, n) f[i][j] = f[i][j] || f[i][k] && f[k][j];
re(i, nx) ed[i].a = ed[i].pre = ed[i].next = i;
if (nx % 2) m = nx + 1; else m = nx;
re(i, nx) {
int t0 = xt[i];
re(j, ny) if (f[t0][j]) add_edge(i, j);
}
}
bool dfs(int x)
{
vst[x] = 1;
int y, x1;
for (int p=ed[x].next; p != x; p=ed[p].next) {
y = ed[p].b; x1 = xz[y];
if (x1 == -1 || !vst[x1] && dfs(x1)) {
xz[y] = x; return 1;
}
}
return 0;
}
void solve()
{
re(i, ny) xz[i] = -1;
re(i, nx) {
re(j, ny) vst[j] = 0;
res += dfs(i);
}
}
void pri()
{
printf("%d\n", nx - res);
}
int main()
{
init();
prepare();
solve();
pri();
return 0;
}
有关图的Dancing Link边表的内容就到此为止了。这真是一种有大用的数据结构。