北航软院17级算法上机自用模板

无权二分图最佳匹配问题：.......................................................1

最大流问题...................................................................................3

寻找最近点对...............................................................................8

寻找最远点对...............................................................................9

凸包：.........................................................................................10

判断线段相交.............................................................................13

判断两个凸多边形是否相交.....................................................14

/* 计算几何基本模板 */..............................................................16

二分图的最小路径覆盖数=|V|-二分图的最大匹配数

*/

/*

匈牙利算法 DFS 版，邻接表形式

添加节点时用 g[i].push_back[j]

*/

#define maxn 1005

int n;

vector<int> g[maxn];

int match[maxn];//记录匹配点

vis[v] = 1;

if(match[v]==-1 || dfs(match[v])) {

match[v] = u;

1

return true;

}

}

}

return false;

}

if(dfs(i))

++ans;

}

return ans;

}

void print(int st, int ed)

{

for(int i=st; i<=ed; ++i)

printf("%d %d\n", match[i], i);

}

/* 注意！有潜在 bug，尽量从 g[1][1]开始记录图！ */

#define maxn 1001

bool g[maxn][maxn];

int maxMatch(int x, int y)

{

int ans = 0;

memset(matchl, -1, sizeof(matchl));

bool flag = false;

while (!q.empty()&&!flag) {

int u=q.front();

2

q.pop();

for(int v=0; v<y&&!flag; ++v) {

if(check[v]!=i&&g[u][v]) {

check[v]=i;

q.push(matchr[v]);

if(matchr[v]>0)

}

}

}

}

if (matchl[i]!=-1)

ans++;

return ans;

}

最大流问题

算法选择：点数大于 1000 使用 Dinic，否则用 SAP

*/

/*

SAP 算法

（没有人能够卡住 SAP！）

一般情况 SAP 算法已经够用了

注意 nodenum 要+1

int g[maxn][maxn];

int gap[maxn], dis[maxn], pre[maxn], cur[maxn];

int sap(int st, int ed, int n)

3

{

memset(cur, 0, sizeof(cur));

memset(dis, 0, sizeof(dis));

memset(gap, 0, sizeof(gap));

int u = pre[st] = st, maxf = 0, k = -1;

gap[0] = n;

pre[v] = u;

u = cur[u] = v;

if(v==ed) {

maxf += k;

for(u = pre[u]; v!=st; v = u, u = pre[u]) {

g[u][v] -= k;

g[v][u] += k;

}

}

goto loop;

for(int v = 0; v < n; ++v)

if(g[u][v] && tmp > dis[v]) {

cur[u] = v;

if((--gap[dis[u]])==0)

break;

gap[dis[u] = tmp + 1]++;

u = pre[u];

SAP 算法（保留原矩阵，可多次使用）

注意 nodenum 要+1

*/

const int maxn = 1100;

int g[maxn][maxn];

4

int gap[maxn], dis[maxn], pre[maxn], cur[maxn];

int flow[maxn][maxn];

int sap(int st, int ed, int n)

{

memset(cur, 0, sizeof(cur));

memset(dis, 0, sizeof(dis));

for (int v = cur[u]; v < n; ++v)

if (g[u][v] - flow[u][v] && dis[u] == dis[v] + 1) {

if (k == -1 || k > g[u][v] - flow[u][v])

k = g[u][v] - flow[u][v];

pre[v] = u;

u = cur[u] = v;

if (v == ed) {

maxf += k;

flow[u][v] += k;

flow[v][u] -= k;

}

goto loop;

}

if (g[u][v] - flow[u][v] && tmp > dis[v]) {

cur[u] = v;

tmp = dis[v];

}

/*

Dinic 算法：

5