《算法竞赛进阶指南》 0x6A 代码 + 杂谈

舞动的晚会
我自己写的 建图可能写错了 导致后面输出的像是可行边 我也很迷 感觉没有检错图

匹配边(i,j) j到i连边
非匹配边 (i,j) i到j连边
匹配的左点i (i,S)
不匹配的左点i (S,i)
匹配的右点j (T,j)
不匹配的右点j (j,T)
然后用Tarjan求强连通分量
(i,j)是可行边的条件：
(i,j)是匹配边 或者 i,j在同一个scc里
那么总边数减去可行边数就是不可行边数，即答案。
注意这个新图要包含源和汇，不能只在二分图两部之间连边，除非原最大匹配是一个完备匹配。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 150000 + 100;

int n, m, k;
int s, t;
int head[maxn], depth[maxn], cur[maxn], cnt;
int nxt[maxn << 2], to[maxn << 2], cap[maxn << 2];  

void ade(int a, int b, int c) {
	to[++cnt] = b;
	cap[cnt] = c;
	nxt[cnt] = head[a];
	head[a] = cnt;
}

bool bfs(){
	queue<int> que;
	que.push(s);
	memset(depth, 0, sizeof(depth));
	depth[s] = 1;
	while(!que.empty()) {
		int u = que.front(); que.pop();
		for(int i = head[u]; i != -1; i = nxt[i]) {
			if(cap[i] > 0 && depth[to[i]] == 0) {
				depth[to[i]] = depth[u] + 1;
				que.push(to[i]);
			}
		}
	}
	if(depth[t]) return 1;
	else return 0;
}

int dfs(int u, int dist) {
	if(u == t) return dist;
	for(int &i = cur[u]; i != -1; i = nxt[i]) {
		if(depth[to[i]] == depth[u] + 1 && cap[i] > 0) {
			int tmp = dfs(to[i], min(dist, cap[i]));
			if(tmp > 0) {
				cap[i] -= tmp;
				cap[i ^ 1] += tmp;
				return tmp; 
			}
		}
	}
	return 0;
}

int dinic() {
	int res = 0, d;
	while(bfs()) {
		for(int i = 0; i < n + m + 5; i ++) cur[i] = head[i];
		while(d = dfs(s, INF)) res += d;
	}
	return res;
}

int dfn[maxn], low[maxn];
bool vis[maxn];
stack<int> stac;
int scc_cnt, idx, cmp[maxn];

int thead[maxn], tcnt;
int tto[maxn << 2], tnxt[maxn << 2];

void tade(int a, int b) {
	tto[++ tcnt] = b;
	tnxt[tcnt] = thead[a];
	thead[a] = tcnt;
}

void tarjan(int x) {
	dfn[x] = low[x] = ++idx;
	stac.push(x);
	vis[x]=true;
	for(int i = thead[x]; i; i = tnxt[i]) {
		int u = tto[i];
		if(!dfn[u]) {
			tarjan(u);
			low[x] = min(low[x], low[u]);
		} else if(vis[u])low[x] = min(low[x], dfn[u]);
	}//tarjan模板
	int k;
	if(low[x] == dfn[x]) {
		++scc_cnt;
		do {
			k = stac.top();
			stac.pop();
			vis[k] = false;
			cmp[k] = scc_cnt;
		} while(x!=k);
	}
}

int a[maxn], b[maxn], e[maxn];

int main() {
	cin >> n >> m >> k;
	memset(head, -1, sizeof(head));
	cnt = -1;
	for(int i = 1; i <= k; i ++) {
		cin >> a[i] >> b[i];
		ade(a[i], b[i] + n, 1), e[i] = cnt;
		ade(b[i] + n, a[i], 0);
	}                                       
	s = 0, t = n + m + 1;
	for(int i = 1; i <= n; i ++) ade(s, i, 1), ade(i, s, 0);
	for(int i = 1; i <= m; i ++) ade(i + n, t, 1), ade(t, i + n, 0);
	dinic();
	
	for(int u = 0; u <= n + m + 1; u ++) for(int i = head[u]; ~i; i = nxt[i])
			if(cap[i]) tade(u, to[i]);

	for(int i = 0; i <= n + m + 1; i ++) 
		if(!dfn[i]) tarjan(i);
		
	int ans = k;
	for(int i = 1; i <= k; i++) 
		if(cmp[a[i]] == cmp[b[i] + n] || !cap[e[i]])
			ans --;

	cout << ans << endl;
	for(int i = 1; i <= k; i ++) {
		if(cmp[a[i]] != cmp[b[i] + n] && cap[e[i]]) {
			cout << i << " ";
		}
	}
	cout << endl;
	return 0;
}

标称

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int inf = 0x3fffffff, u = 40010, w = 300010;
int head[u], ver[w], edge[w], Next[w], d[u], e[w], c[u], sta[u], ins[u], dfn[u], low[u];
int n, m, p, s, t, i, j, tot, maxflow, ans, x, y, scc, st, num;
char str[10];
vector<int> a[u];
queue<int> q;

void add(int x, int y, int z) {
	ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
	ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}

bool bfs() {
	memset(d, 0, sizeof(d));
	while (q.size()) q.pop();
	q.push(s);
	d[s] = 1;
	while (q.size()) {
		int x = q.front();
		q.pop();
		for (int i = head[x]; i; i = Next[i])
			if (edge[i] && !d[ver[i]]) {
				q.push(ver[i]);
				d[ver[i]] = d[x] + 1;
				if (ver[i] == t) return 1;
			}
	}
	return 0;
}

int dinic(int x, int flow) {
	if (x == t) return flow;
	int rest = flow, k;
	for (int i = head[x]; i && rest; i = Next[i])
		if (edge[i] && d[ver[i]] == d[x] + 1) {
			k = dinic(ver[i], min(rest, edge[i]));
			if (!k) d[ver[i]] = 0;
			edge[i] -= k;
			edge[i ^ 1] += k;
			rest -= k;
		}
	return flow - rest;
}

void add2(int x, int y) {
	a[x].push_back(y);
}

void tarjan(int x) {
	dfn[x] = ++num;
	low[x] = num;
	sta[++st] = x;
	ins[x] = 1;
	int y;
	for (int i = 0; i<a[x].size(); i++)
		if (!dfn[y = a[x][i]]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
		} else if (ins[y]) low[x] = min(low[x], dfn[y]);
	if (dfn[x] == low[x]) {
		scc++;
		do {
			y = sta[st];
			st--;
			ins[y] = 0;
			c[y] = scc;
		} while (x != y);
	}
}

int main() {
	while (cin >> n >> m >> p) {
		memset(head, 0, sizeof(head));
		s = 0, t = n + m + 1;
		tot = 1;
		maxflow = 0;
		for (i = 1; i <= n; i++) add(s, i, 1);
		for (i = 1; i <= m; i++) add(i + n, t, 1);
		for (i = 1; i <= p; i++) {
			scanf("%d%d", &x, &y);
			add(x, n + y, 1), e[i] = tot;
		}
		while (bfs())
			while (i = dinic(s, inf)) maxflow += i;
		for (i = s; i <= t; i++) a[i].clear();
		for (i = 1; i <= p; i++)
			if (!edge[e[i]]) add2(ver[e[i]], ver[e[i] ^ 1]);
			else add2(ver[e[i] ^ 1], ver[e[i]]);
		for (i = 1; i <= n; i++)
			if (!edge[2 * i]) add2(i, s);
			else add2(s, i);
		for (i = 1; i <= m; i++)
			if (!edge[2 * (n + i)]) add2(t, n + i);
			else add2(n + i, t);
		memset(dfn, 0, sizeof(dfn));
		memset(ins, 0, sizeof(ins));
		memset(c, 0, sizeof(c));
		st = num = scc = ans = 0;
		for (i = s; i <= t; i++)
			if (!dfn[i]) tarjan(i);
		for (i = 1; i <= p; i++)
			if (edge[e[i]] || c[ver[e[i]]] == c[ver[e[i] ^ 1]]) ans++;
		cout << (ans = p - ans) << endl;
		if (!ans) cout << endl;
		for (i = 1; i <= p; i++)
			if (!edge[e[i]] && c[ver[e[i]]] != c[ver[e[i] ^ 1]])
				if (--ans) printf("%d ", i);
				else printf("%d\n", i);
	}
}