搞完了網(wǎng)絡(luò)流圖，搞完了一般圖，最后應(yīng)該是二分圖了（在本沙茶知道的圖的范圍內(nèi)）
二分圖的邊有些特別，邊<a, b>并不是表示從a到b的邊，而是從X方點a（簡記為X
a）到Y(jié)方點b（簡記為Y
b）的邊。在二分圖中，邊其實是無向的，但由于大多數(shù)引用的時候都是X方點引用Y方點，所以可以把邊看成有向的（如果實在要逆向引用的話，加一條逆向邊吧囧……）
邊類型定義（和一般圖完全一致。這里是不帶權(quán)的，如果像KM算法里面有帶權(quán)邊，加一個len域即可）：
struct edge {
int a, b, pre, next;
} ed[MAXM];
關(guān)鍵是在初始化表頭的時候，設(shè)圖中有NX個X方點和NY個Y方點，則單點鏈表數(shù)其實只有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邊表實現(xiàn)的Hungary算法的深度優(yōu)先遍歷部分：
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是否被訪問的標(biāo)志，在每次遍歷前，vst都要全部清零。
【應(yīng)用實例】
PKU1087題意很難懂，其實就是：房間里有N個插座，每個插座都有一個型號（沒有兩個插座的型號相同），現(xiàn)在要把M個用電器插到這N個插座里，每個用電器有一個默認(rèn)型號，表示該用電器只能插到其默認(rèn)型號的插座里（有可能有的用電器的默認(rèn)型號不與房間里的任意一個插座對應(yīng)，如樣例中的X型號）。有K種適配器（每種適配器可以用無限次），每一種適配器都有兩個參數(shù)S1和S2，表示該種適配器使用一次可以將某個默認(rèn)型號為S1的用電器的默認(rèn)型號改為S2（同一個用電器可以被多次改變默認(rèn)型號）。問在使用了若干次適配器后，最少有多少個用電器插不到插座里？
首先將每種型號作為一個點，若某種適配器的兩個參數(shù)分別為S1和S2則連邊<S1, S2>，對這個有向圖求傳遞閉包。然后再建一個二分圖，X方點表示用電器，Y方點表示插座，若X
i的初始默認(rèn)型號在一開始建的有向圖中可以到達(dá)Y
j的型號（用傳遞閉包直接得到），則連邊(X
i, Y
j)。對這個二分圖求最大匹配，則(M - 最大匹配值)就是結(jié)果。
代碼：
#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;
}
有關(guān)圖的Dancing Link邊表的內(nèi)容就到此為止了。這真是一種有大用的數(shù)據(jù)結(jié)構(gòu)。