HDU 1151 Air Raid（最小路徑覆蓋）
二分圖匹配（匈牙利算法的DFS實現）
初始化：g[][]兩邊頂點的劃分情況
建立g[i][j]表示i->j的有向邊就可以了，是左邊向右邊的匹配
g沒有邊相連則初始化為0
uN是匹配左邊的頂點數，vN是匹配右邊的頂點數
調用：res=hungary();輸出最大匹配數
優點：適用於稠密圖，DFS找增廣路，實現簡潔易於理解
時間復雜度:O(VE)
***************************************************************************/
頂點編號從0開始的
/*
HDU 1151*/
#include
#include
#include
#include
using namespace std;
/* **************************************************************************
//二分圖匹配（匈牙利算法的DFS實現）
//初始化：g[][]兩邊頂點的劃分情況
//建立g[i][j]表示i->j的有向邊就可以了，是左邊向右邊的匹配
//g沒有邊相連則初始化為0
//uN是匹配左邊的頂點數，vN是匹配右邊的頂點數
//調用：res=hungary();輸出最大匹配數
//優點：適用於稠密圖，DFS找增廣路，實現簡潔易於理解
//時間復雜度:O(VE)
//***************************************************************************/
//頂點編號從0開始的
const int MAXN=150;
int uN,vN;//u,v數目
int g[MAXN][MAXN];
int linker[MAXN];
bool used[MAXN];
bool dfs(int u)//從左邊開始找增廣路徑
{
int v;
for(v=0;v
