怎么修改网站上传附件大小,wordpress不能播放wmv,珠宝销售网站源码,网站模板批量下载题目显然可以转化为求每一条边对二分图最大独立集的贡献#xff0c;二分图最大独立集\(\)点数\(-\)最大匹配数#xff0c;我们就有了\(50pts\)做法。 正解的做法是在原图上跑\(Tarjan\)#xff0c;最开始我想复杂了#xff0c;后来才意识到#xff0c;只要存在这样一个强连…题目显然可以转化为求每一条边对二分图最大独立集的贡献二分图最大独立集\(\)点数\(-\)最大匹配数我们就有了\(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);}
} 转载于:https://www.cnblogs.com/maomao9173/p/10638348.html
