network.cpp

ACM经典算法ACM经典算法ACM经典算法

/*============================================================*\
 | 二分图匹配(邻接矩阵)                                       |
 | INIT: g[][]邻接矩阵;                                       |
 | CALL: res = match(nva, nvb);                               |
\*============================================================*/
int g[N][N], q[N], pv[N], ma[N], mb[N];
int match(int nva, int nvb)     // nva: |X|, nvb: |Y|
{
	int i, j, x, qs, qe, res = 0;
	memset(ma, -1, sizeof(ma));
	memset(mb, -1, sizeof(mb));
	for (i = 0; i < nva; i++) { // vertex: 0 ~ n-1
		qs = qe = 0;
		for (j = 0; j < nvb; j++) pv[j] = -2;
		for (j = 0; j < nvb; j++) if (g[i][j]) {
            pv[j] = -1; q[qe++] = j;
		}
		while (qs < qe) {
			if (-1 == mb[x = q[qs]]) break;
			for (qs++, j = 0; j < nvb; j++)
				if(-2 == pv[j] && g[ mb[x] ][j]) {
					pv[j] = x; q[qe++] = j;
				}
		}
		if (qs == qe) continue;
		while (pv[x] > -1) {
			ma[ mb[ pv[x] ] ] = x;
			mb[x] = mb[ pv[x] ];
			x = pv[x];
		}
		mb[x] = i; ma[i] = x; res++;
	}
	return res;
}
/*============================================================*\
 | 二分图匹配(邻接表)                                         |
 | INIT: edge[][]为邻接表; deg[i]为i的相邻点个数; adj[]置-1;  |
 | CALL: res = match(n);                                      |
\*============================================================*/
int path[N], vis[N], adj[N], deg[N], edge[N][N];
int sear(int who, int cnt)
{
	int i, rcnt, con;
	if (0 == vis[who]) {
		vis[who] = 1;
		for (i = 0; i < deg[who]; ++i) {
			con = adj[ edge[who][i] ];
			path[cnt] = edge[who][i];
			if (-1 == con) return cnt + 1;
			rcnt = sear(con, cnt + 1);
			if (rcnt) return rcnt;
		}
	}
	return 0;
}
int match(int n)
{
	int i, j, k, tmp, cur, res = n;
	memset(adj, -1, sizeof(adj));
    for (i = 0; i < n; ++i) {    // vertex: 0 ~ n-1
		memset(vis, 0, sizeof(vis));
		k = sear(i, 0);
		res -= !k;
		for (cur = i, j = 0; j < k; ++j) {
			tmp = adj[ path[j] ];
			adj[ path[j] ] = cur;
			cur = tmp;
		}
    }
	return res / 2;
}
/*============================================================*\
 | 二分图最大权匹配 O(N^3)                                    |
 | INIT: cost[][]置为费用表;                                  |
 | CALL: res = match(n);                                      |
 | 注: cost[i][j], i属于X集合, j属于Y集合, 且|X|==|Y|==n;     |
 |     尾部有 EQUAL 注释的行, 当费用为double时最好改一下;     |
\*============================================================*/
#define typec int                       // type of cost
const typec inf = 0x3f3f3f3f;           // max of cost
queue<int> que;
int pv[N], vx[N], vy[N], mx[N], my[N];
typec cost[N][N], lx[N], ly[N], slk[N];
int bfs(int n)
{
	int i, p, t, u; typec ex;
	while (!que.empty()) {
		p = que.front(); que.pop(); u = p >> 1;
		if (p & 1) {
			if (-1 == my[u]) {
				for ( ; u != -1; u = t) {
					t = mx[ my[u] = pv[u] ];
					mx[ pv[u] ] = u;
				}
				return 1;
			} else {
				vx[ my[u] ] = 1; que.push(my[u] << 1);
			}
		} else {
			for (i = 0; i < n; i++) {
				if (vy[i]) continue;
				else if (lx[u] + ly[i] != cost[u][i]) { // EQUAL
					ex = lx[u] + ly[i] - cost[u][i];
					if (slk[i] > ex) {
						slk[i] = ex; pv[i] = u;
					}
				} else {
					vy[i] = 1; pv[i] = u;
					que.push((i << 1) | 1);
				}
			}
		}
	}
	return 0;
}
typec match(int n)
{
	typec res = 0, ex;
	int agu = 1, mn, i, j;
	memset(ly, 0, sizeof(ly));
	memset(mx, -1, sizeof(mx));
	memset(my, -1, sizeof(my));
	for (i = 0; i < n; i++) {                 // vertex: 0 ~ n-1
		lx[i] = - inf;
		for (j = 0; j < n; j++)
			if (lx[i] < cost[i][j]) lx[i] = cost[i][j];
	}
	for (mn = 0; mn < n; mn++) {
		if (agu) {
			memset(vx, 0, sizeof(vx));
			memset(vy, 0, sizeof(vy));
			for (i = 0; i < n; i++) slk[i] = inf;
			while (!que.empty()) que.pop();
			que.push(mn << 1); vx[mn] = 1;
		}
		if (bfs(n)) { agu = 1; continue; }
		ex = inf; mn--; agu = 0;
		for (i = 0; i < n; i++)
			if (!vy[i] && ex > slk[i]) ex = slk[i];
		for (i = 0; i < n; i++) {
			if (vx[i]) lx[i] -= ex;
			if (vy[i]) ly[i] += ex;
			slk[i] -= ex;
		}
		for (i = 0; i < n; i++)
			if (!vy[i] && 0 == slk[i]) {      // EQUAL
				vy[i] = 1; que.push((i << 1) | 1);
			}
	}
	for (i = 0; i < n; i++) res += cost[i][ mx[i] ];
	return res;
}
/*============================================================*\
 | 无向图最小割 O(N^3)                                        |
 | INIT: 初始化邻接矩阵g[][];                                 |
 | CALL: res = mincut(n);                                     |
 | 注: Stoer-Wagner Minimum Cut;                              |
\*============================================================*/
#define typec int                   // type of res
const typec inf = 0x3f3f3f3f;       // max of res
const typec maxw = 1000;            // maximum edge weight
typec g[V][V], w[V];
int a[V], v[V], na[V];
typec mincut(int n)
{
	int i, j, pv, zj;
	typec best = maxw * n * n;
    for (i = 0; i < n; i++) v[i] = i;  // vertex: 0 ~ n-1
    while (n > 1) {
        for (a[v[0]] = 1, i = 1; i < n; i++) {
            a[v[i]] = 0; na[i - 1] = i;
            w[i] = g[v[0]][v[i]];
        }
        for (pv = v[0], i = 1; i < n; i++ ) {
            for (zj = -1, j = 1; j < n; j++ )
                if (!a[v[j]] && (zj < 0 || w[j] > w[zj])) zj = j;
			a[v[zj]] = 1;
			if (i == n - 1) {
				if (best > w[zj]) best = w[zj];
				for (i = 0; i < n; i++)
					g[v[i]][pv] = g[pv][v[i]] += g[v[zj]][v[i]];
				v[zj] = v[--n];
				break;
			}
			pv = v[zj];
			for (j = 1; j < n; j++) if(!a[v[j]])
				w[j] += g[v[zj]][v[j]];
        }
    }
    return best;
}
/*============================================================*\
 | 有上下界的最小(最大)流                                     |
 | INIT: up[][]为容量上界; low[][]为容量下界;                 |
 | CALL: mf = limitflow(n, src, sink); flow[][]中为流量分配;  |
 | 另附: 循环流问题                                           |
 | 描述: 无源无汇的网络N, 设N是具有基础有向图D=(V，A)的网络.  |
 |       l和c分别为容量下界和容量上界. 如果定义在A上的函数    |
 |       f满足: f(v, V) = f(V, v). V中任意顶点v,              |
 |       l(a)<=f(a)<=c(a), 则称f为网络N的循环流.              |
 | 解法: 添加一个源s和汇t，对于每个下限容量l不为0的边(u, v),  |
 |       将其下限去掉, 上限改为c-l, 增加两条边(u, t), (s, v), |
 |       容量均为l. 原网络存在循环流等价于新网络最大流是满流. |
\*============================================================*/
int up[N][N], low[N][N], flow[N][N];
int pv[N], que[N], d[N];
void maxflow(int n, int src, int sink)
{   // BFS增广, O(E * maxflow)
    int p, q, t, i, j;
    do{
        for (i = 0; i < n; pv[i++] = 0) ;
        pv[t = src] = src + 1; d[t] = inf;
        for (p=q=0; p<=q && !pv[sink]; t=que[p++])
            for (i=0; i<n; i++) {
                if (!pv[i]&&up[t][i]&&(j=up[t][i]-flow[t][i])>0)
                    pv[que[q++]=i]=+t+1, d[i]=d[t]<j?d[t]:j;
                else if (!pv[i]&&up[i][t]&&(j=flow[i][t])>0)
                    pv[que[q++]=i]=-t-1, d[i]=d[t]<j?d[t]:j;
			}
		for (i=sink; pv[i] && i!=src; ) {
            if (pv[i]>0) flow[pv[i]-1][i]+=d[sink], i=pv[i]-1;
            else flow[i][-pv[i]-1]-=d[sink], i=-pv[i]-1;
		}
    } while (pv[sink]);
}
int limitflow(int n, int src, int sink)
{
    int i, j, sk, ks;
    if (src == sink) return inf;
	up[n][n+1] = up[n+1][n] = up[n][n] = up[n+1][n+1] = 0;
    for (i = 0; i < n; i++) {
		up[n][i] = up[i][n] = up[n+1][i] = up[i][n+1] = 0;
        for (j = 0; j < n; j++) {
            up[i][j] -= low[i][j];
			up[n][i] += low[j][i];
			up[i][n+1] += low[i][j];
		}
	}
    sk = up[src][sink]; ks = up[sink][src];
    up[src][sink] = up[sink][src] = inf;
    maxflow(n+2, n, n+1);
    for (i = 0; i < n; i++)
        if (flow[n][i] < up[n][i]) return -1;
    flow[src][sink] = flow[sink][src] = 0;
    up[src][sink] = sk; up[sink][src] = ks;
	// ! min: src <- sink;   max: src -> sink;
    maxflow(n, sink, src);
    for (i = 0; i < n; i++) for (j = 0; j < n; j++) {
        up[i][j] += low[i][j]; flow[i][j] += low[i][j];
	}
    for (j = i = 0; i < n; j += flow[src][i++]) ;
    return j;
}
/*============================================================*\
 | Dinic最大流 O(V^2 * E)                                     |
 | INIT: ne=2; head[]置为0; addedge()加入所有弧;              |
 | CALL: flow(n, s, t);                                       |
\*============================================================*/
#define typec int                   // type of cost
const typec inf = 0x3f3f3f3f;       // max of cost
struct edge { int x, y, nxt; typec c; } bf[E];
int ne, head[N], cur[N], ps[N], dep[N];
void addedge(int x, int y, typec c)
{	// add an arc(x -> y, c); vertex: 0 ~ n-1;
	bf[ne].x = x; bf[ne].y = y; bf[ne].c = c;
	bf[ne].nxt = head[x]; head[x] = ne++;
	bf[ne].x = y; bf[ne].y = x; bf[ne].c = 0;
	bf[ne].nxt = head[y]; head[y] = ne++;
}
typec flow(int n, int s, int t)
{
	typec tr, res = 0;
    int i, j, k, f, r, top;
    while (1) {
        memset(dep, -1, n * sizeof(int));
		for (f = dep[ps[0] = s] = 0, r = 1; f != r; )
			for (i = ps[f++], j = head[i]; j; j = bf[j].nxt) {
				if (bf[j].c && -1 == dep[k = bf[j].y]) {
					dep[k] = dep[i] + 1; ps[r++] = k;
					if (k == t) { f = r; break; }
				}
			}
        if (-1 == dep[t]) break;

        memcpy(cur, head, n * sizeof(int));
        for (i = s, top = 0; ; ) {
            if (i == t) {
                for (k = 0, tr = inf; k < top; ++k)
					if (bf[ps[k]].c < tr) tr = bf[ps[f = k]].c;
                for (k = 0; k < top; ++k)
                    bf[ps[k]].c -= tr, bf[ps[k]^1].c += tr;
                res += tr;  i = bf[ps[top = f]].x;
            }
            for (j=cur[i]; cur[i]; j = cur[i] = bf[cur[i]].nxt)
                if (bf[j].c && dep[i]+1 == dep[bf[j].y]) break;
            if (cur[i]) {
                ps[top++] = cur[i];