二次聯(lián)通門 :?luogu P1231 教輔的組成

?

?

?

?

/*luogu P1231 教輔的組成拆點 + 最大流把書拆點后與答案與資料連邊跑最大流 */ #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <queue>#define Max 50005 #define INF 1e7using namespace std;void read (int &now) {now = 0;char word = getchar ();while (word > '9' || word < '0')word = getchar ();while (word >= '0' && word <= '9'){now = now * 10 + word - '0';word = getchar ();} }struct Edge {int to;int next;int flow; }edge[Max << 3];int Edge_Count = 1; int edge_list[Max];inline void AddEdge (int from, int to) {Edge_Count++;edge[Edge_Count].flow = 1;edge[Edge_Count].to = to;edge[Edge_Count].next = edge_list[from];edge_list[from] = Edge_Count;Edge_Count++;edge[Edge_Count].to = from;edge[Edge_Count].flow = 0;edge[Edge_Count].next = edge_list[to];edge_list[to] = Edge_Count; }int N, M, Q; int E; int S, T; int deep[Max]; int Answer;int Flowing (int now, int flow) {if (flow <= 0 || now == T)return flow;int pos = 0, res = 0;for (int i = edge_list[now]; i; i = edge[i].next){if (deep[edge[i].to] != deep[now] + 1 || edge[i].flow <= 0)continue;pos = Flowing (edge[i].to, min (edge[i].flow, flow));flow -= pos;res += pos;edge[i].flow -= pos;edge[i ^ 1].flow += pos;if (flow <= 0)return res;}return res; }int main (int argc, char *argv[]) {read (N);read (M);read (Q);read (E);M += N;Q += M;S = Max - 2;T = Max - 3;int x, y;for (int i = 1; i <= N; i++)AddEdge (i, i + Q);for (int i = N + 1; i <= M; i++)AddEdge (S, i);for (int i = M + 1; i <= Q; i++)AddEdge (i, T);for (int i = 1; i <= E; i++){read (x);read (y);AddEdge (y + N, x);}read (E);for (int i = 1; i <= E; i++){read (x);read (y);AddEdge (x + Q, y + M);}while (true){bool flag = false;memset (deep, -1, sizeof deep);queue <int> Queue;Queue.push (S);deep[S] = 0;int now;while (!Queue.empty ()){now = Queue.front ();Queue.pop ();for (int i = edge_list[now]; i; i = edge[i].next)if (deep[edge[i].to] < 0 && edge[i].flow){deep[edge[i].to] = deep[now] + 1;if (edge[i].to == T){flag = true;break;}Queue.push (edge[i].to); }if (flag)break;}if (deep[T] < 0)break;Answer += Flowing (S, INF);}printf ("%d", Answer);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ZlycerQan/p/6882689.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的luogu P1231 教辅的组成的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。