Luogu P3731 [HAOI2017]新型城市化

題目顯然可以轉化為求每一條邊對二分圖最大獨立集的貢獻，二分圖最大獨立集\(=\)點數\(-\)最大匹配數，我們就有了\(50pts\)做法。

正解的做法是在原圖上跑\(Tarjan\)，最開始我想復雜了，后來才意識到，只要存在這樣一個強連通分量，那么斷掉分量內的任意一條邊都不會破壞其連通性，即不管刪掉哪個連邊都一定會有新的匹配補充。只要讓兩個點不在同一個分量里面，而且原來是滿流的（匹配可行邊），那么它就是一個可用邊（匹配必須邊）。

#include <bits/stdc++.h>
using namespace std;const int N = 400010;
const int M = 800010;
const int INF = 0x3f3f3f3f;struct Graph {int cnt, head[N];struct edge {int nxt, to, f;}e[M];Graph () {cnt = -1;memset (head, -1, sizeof (head));}void add_edge (int u, int v, int f) {e[++cnt] = (edge) {head[u], v, f}; head[u] = cnt;}void add_len (int u, int v, int f) {add_edge (u, v, f);add_edge (v, u, 0);}queue <int> q;int cur[N], deep[N];bool bfs (int s, int t) {memcpy (cur, head, sizeof (head));memset (deep, 0x3f, sizeof (deep));deep[s] = 0; q.push (s);while (!q.empty ()) {int u = q.front (); q.pop ();for (int i = head[u]; ~i; i = e[i].nxt) {int v = e[i].to;if (deep[v] == INF && e[i].f) {deep[v] = deep[u] + 1;q.push (v);}}}return deep[t] != INF;}int dfs (int u, int t, int lim) {if (u == t || !lim) {return lim;}int tmp = 0, flow = 0;for (int &i = cur[u]; ~i; i = e[i].nxt) {int v = e[i].to;if (deep[v] == deep[u] + 1) {tmp = dfs (v, t, min (lim, e[i].f));lim -= tmp;flow += tmp;e[i ^ 0].f -= tmp;e[i ^ 1].f += tmp;if (!lim) break;}}return flow;}int Dinic (int s, int t) {int max_flow = 0;while (bfs (s, t)) {max_flow += dfs (s, t, INF);}return max_flow;}
}G;int n, m, _ans, id[N];struct Query {int u, v;bool operator < (Query rhs) const {return u == rhs.u ? v < rhs.v : u < rhs.u;}   bool operator == (Query rhs) const {return u == rhs.u && v == rhs.v;}
}q[N], ans[N];int A (int x) {return n * 0 + x;}
int B (int x) {return n * 1 + x;}int read () {int s = 0, w = 1, ch = getchar ();while ('9' < ch || ch < '0') {if (ch == '-') w = -1;ch = getchar ();}while ('0' <= ch && ch <= '9') {s = s * 10 + ch - '0';ch = getchar ();}return s * w;
} stack <int> sta;
int dfn[N], low[N], col[N], vis[N]; void Tarjan (int u) {sta.push (u);vis[u] = true;dfn[u] = low[u] = ++dfn[0]; for (int i = G.head[u]; ~i; i = G.e[i].nxt) {int v = G.e[i].to;if (!G.e[i].f) continue;if (!dfn[v]) {Tarjan (v);low[u] = min (low[u], low[v]);} else if (vis[v]) {low[u] = min (low[u], dfn[v]);}}if (dfn[u] == low[u]) {int tmp; ++col[0];do {tmp = sta.top ();vis[tmp] = false;col[tmp] = col[0];sta.pop ();}while (tmp != u);}
}int main () {cin >> n >> m;int s = n * 2 + 1;int t = n * 2 + 2;for (int i = 1; i <= m; ++i) {q[i].u = read ();q[i].v = read ();if (q[i].u > q[i].v) {swap (q[i].u, q[i].v);}}sort (q + 1, q + 1 + m);for (int i = 1; i <= m; ++i) {id[i] = G.cnt + 1;G.add_len (A (q[i].u), B (q[i].v), 1);G.add_len (A (q[i].v), B (q[i].u), 1);}for (int i = 1; i <= n; ++i) {G.add_len (s, A (i), 1);G.add_len (B (i), t, 1);}G.Dinic (s, t);for (int i = 1; i <= t; ++i) {if (!dfn[i]) {Tarjan (i);}}for (int i = 1; i <= m; ++i) {if (col[A (q[i].u)] != col[B (q[i].v)] && !G.e[id[i]].f) {ans[++_ans] = q[i];}}cout << _ans << endl;for (int i = 1; i <= _ans; ++i) {printf ("%d %d\n", ans[i].u, ans[i].v);}
}