舞动的夜晚
C++ 代码
/*
本题是让我们求二分图的不可行边。且不保证二分图的最大匹配是一组完备匹配。
在一般二分图中,可以用最大流计算出任意一组最大匹配。此时:
必须边的判定条件为:(x, y) 流量为 1,并且在残量网络上属于不同的强连通分量。
可行边的判定条件为:(x, y) 流量为 1,或者在残量网络上属于同一个强连通分量。
不可行边的判定条件为:(x, y) 流量为 0,并且在残量网络上属于不同的强连通分量。
因此,用Dinic算法求最大流,建立残量网络后,用Tarjan算法求强连通分量,再根据定义逐一找出不可行边。
*/
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20010, M = 400010, INF = 0x3f3f3f3f;
int n, m, p, S, T;
//h[] 表示原网路的表头
//hr[] 表示残量网络的表头
int h[N], hr[N], e[M], w[M], ne[M], idx; //邻接表
int edge[M]; //edge[i] 记录第i对关系对应的边的编号
int d[N]; //记录每个节点的层数
int now[N]; //记录每个表头指针的位置
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], scc_cnt;
bool in_stk[N];
int q[N]; //队列
int maxf; //记录最大流量
void add1(int a, int b, int c) //原网络建边
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}
void add2(int a, int b) //残量网络建边
{
e[idx] = b, ne[idx] = hr[a], hr[a] = idx++;
}
bool bfs() //判断是否存在增广路径
{
int hh = 0, tt = 0;
q[0] = S;
memset(d, 0, sizeof d);
d[S] = 1;
now[S] = h[S];
while(hh <= tt)
{
int t = q[hh++];
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(!w[i] || d[j]) continue;
d[j] = d[t] + 1;
now[j] = h[j];
q[++tt] = j;
if(j == T) return true; //存在增广路径
}
}
return false; //不存在增广路径
}
int dinic(int u, int flow) //从u节点往下传送流量
{
if(u == T) return flow;
int rest = flow;
for(int i = now[u]; i != -1 && rest; i = ne[i]) //还有流量就往下传输
{
int j = e[i];
now[u] = i;
if(w[i] && d[j] == d[u] + 1) //能通过当前边往下传输流量
{
int k = dinic(j, min(rest, w[i]));
if(!k) d[j] = 0; //无法往当前分支传输,直接剪掉
w[i] -= k;
w[i ^ 1] += k;
rest -= k; //减去传输下去的流量
}
}
return flow - rest; //返回真正传输的流量
}
void tarjan(int u) //求强连通分量
{
dfn[u] = low[u] = ++timestamp;
stk[++top] = u, in_stk[u] = true;
for(int i = hr[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if(in_stk[j])
low[u] = min(low[u], dfn[j]);
}
if(dfn[u] == low[u])
{
++scc_cnt;
int y;
do
{
y = stk[top--];
in_stk[y] = false;
id[y] = scc_cnt;
} while(y != u);
}
}
int main()
{
while(cin >> n >> m >> p)
{
//初始化邻接表
memset(h, -1, sizeof h);
memset(hr, -1, sizeof hr);
idx = 0;
S = 0, T = n + m + 1; //起点、终点
for(int i = 1; i <= n; i++) add1(S, i, 1); //从起点向左部节点连边
for(int i = 1; i <= m; i++) add1(i + n, T, 1); //从右部节点向终点连边
for(int i = 1; i <= p; i++) //从左部节点向右部节点连边
{
int a, b;
scanf("%d%d", &a, &b);
add1(a, b + n, 1); //添加边
edge[i] = idx - 1; //记录每对关系对应的边的编号
}
//dinic算法
maxf = 0;
int flow = 0;
while(bfs())
while(flow = dinic(S, INF)) maxf += flow;
//建残量网路
for(int i = 1; i <= p; i++) //建左部节点和右部节点之间的边
if(!w[edge[i]]) add2(e[edge[i]], e[edge[i] ^ 1]); //非匹配边,从左向右连边
else add2(e[edge[i] ^ 1], e[edge[i]]); //匹配边,从右向左连边
for(int i = 1; i <= n; i++) //建起点和左部节点之间的边(正常建边即可)
if(!w[2 * (i - 1)]) add2(i, S); //非匹配边,从右向左连边
else add2(S, i); //匹配边,从左向右连边
for(int i = 1; i <= m; i++) //建右部节点和终点之间的边(正常建边即可)
if(!w[2 * (i - 1 + n)]) add2(T, i + n); //非匹配边,从右向左连边
else add2(i + n, T); //匹配边,从左向右连边
//求强连通分量
memset(dfn, 0, sizeof dfn);
memset(id, 0, sizeof id);
memset(in_stk, 0, sizeof in_stk);
scc_cnt = timestamp = top = 0;
for(int i = S; i <= T; i++)
if(!dfn[i])
tarjan(i);
int res = 0; //记录不可行边的数量
for(int i = 1; i <= p; i++)
if(!w[edge[i]] && id[e[edge[i]]] != id[e[edge[i] ^ 1]]) res++;
printf("%d\n", res);
for(int i = 1; i <= p; i++)
if(!w[edge[i]] && id[e[edge[i]]] != id[e[edge[i] ^ 1]])
if(res--) printf("%d ", i);
puts("");
}
return 0;
}