[luoguP2805] [NOI2009]植物大战僵尸（网络流）

传送门

结论：这是最大权闭合图的模型

因为可能A保护B，B保护A，出现环。

所以由植物A向植物A保护的植物连边，然后拓扑排序，将环去掉。

然后将拓扑排序的边反向连，建立最大权闭合图的模型。

跑最大流（最小割），用正权边之和最小割即为答案

#include <queue>#include <cstdio>#include <vector>#include <cstring>#include <iostream>#define N 1000001#define id(i, j) ((i  1) * m + j)using namespace std;int n, m, s, t, T, cnt, sum;int head[N], to[N], nex[N], val[N], a[N], dis[N], cur[N], d[N];vector <int> vec[N];queue <int> q;inline int read()inline void add(int x, int y, int z)inline bool bfs()}}return 0;}inline int dfs(int u, int maxflow)}return used;}inline int dinic()return ret;}int main()T = read();while(T)}for(i = 1; i <= n * m; i++)if(!d[i]) q.push(i);while(!q.empty())for(u = 1; u <= n * m; u++)if(!d[u])}printf("%d\n", sum  dinic());return 0;}

上一篇：[Vijos1308]埃及分数（迭代加深搜索 + 剪枝）

下一篇：[luoguP2518][HAOI2010]计数（数位DP）