[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=1565
[算法]
首先 ， 题目中的约束条件可以概括为"若选A , 则必须选B"
建图后解最大权闭合子图即可
注意原图中在环上的点和能走到环上的点都不能选
时间复杂度 : O(dinic(N , M))
[代码]
#include<bits/stdc++.h> using namespace std; #define N 2010 typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int inf = 2e9; struct edge { int to , w , nxt; } e[N * 2000]; int n , m , total , tot , S , T , timer , cnt; int head[N] , dep[N] , low[N] , dfn[N] , score[N] , belong[N] , sz[N]; int point[N][N]; bool instack[N] , ok[N]; vector< int > a[N]; stack< int > s; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); } template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } inline void addedge(int u , int v , int w) { ++tot; e[tot] = (edge){v , w , head[u]}; head[u] = tot; ++tot; e[tot] = (edge){u , 0 , head[v]}; head[v] = tot; } inline bool bfs() { queue< int > q; q.push(S); for (int i = 1; i <= T; i++) dep[i] = -1; dep[S] = 1; while (!q.empty()) { int cur = q.front(); q.pop(); for (int i = head[cur]; i; i = e[i].nxt) { int v = e[i].to , w = e[i].w; if (w > 0 && dep[v] == -1) { dep[v] = dep[cur] + 1; q.push(v); if (v == T) return true; } } } return false; } inline int dinic(int u , int flow) { int rest = flow; if (u == T) return flow; for (int i = head[u]; i && rest; i = e[i].nxt) { int v = e[i].to , w = e[i].w; if (w > 0 && dep[v] == dep[u] + 1) { int k = dinic(v , min(w , rest)); if (!k) dep[v] = 0; rest -= k; e[i].w -= k; e[i ^ 1].w += k; } } return flow - rest; } inline void tarjan(int u) { dfn[u] = low[u] = ++timer; instack[u] = true; s.push(u); for (unsigned i = 0; i < a[u].size(); i++) { int v = a[u][i]; if (!dfn[v]) { tarjan(v); chkmin(low[u] , low[v]); } else if (instack[v]) chkmin(low[u] , dfn[v]); } if (low[u] == dfn[u]) { int v = 0; ++cnt; do { v = s.top(); s.pop(); instack[v] = false; belong[v] = cnt; ++sz[cnt]; } while (v != u); } } inline void dfs(int u) { ok[u] = false; for (unsigned i = 0; i < a[u].size(); i++) if (ok[a[u][i]]) dfs(a[u][i]); } int main() { read(n); read(m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { point[i][j] = ++total; } } S = total + 1 , T = S + 1; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { read(score[point[i][j]]); int x; read(x); while (x--) { int bx , by; read(bx); read(by); a[point[i][j]].push_back(point[bx][by]); } } } for (int i = 0; i < n; i++) { for (int j = 1; j < m; j++) { a[point[i][j]].push_back(point[i][j - 1]); } } memset(ok , true , sizeof(ok)); for (int i = 1; i <= total; i++) if (!dfn[i]) tarjan(i); for (int i = 1; i <= total; i++) if (sz[belong[i]] > 1 && ok[i]) dfs(i); int ans = 0; tot = 1; for (int i = 1; i <= total; i++) { if (!ok[i]) continue; if (score[i] >= 0) { ans += score[i]; addedge(S , i , score[i]); } else addedge(i , T , -score[i]); for (unsigned j = 0; j < a[i].size(); j++) if (ok[a[i][j]]) addedge(a[i][j] , i , inf); } while (bfs()) { while (int flow = dinic(S , inf)) ans -= flow; } printf("%d " , ans); return 0; }