题目大意
简述一下： 有n个布尔变量，开始时分别是0或1。你可以改变这些变量，改变（0变1，1变0）第i个变量的代价是v[i] 现在有m个限制，形如a，b，x1，x2，x3…，xk，表示希望x1-xk都是a（a为0或1），都满足后可以获得b的价值 有一些限制如果没有满足要倒扣g的价值，g对于所有限制是一个相同的值 求最后能获得的最大价值
思路
一眼网络流
一个错误的思路：假设我们只考虑1，那么每个人到s连边，每个人到ta希望是1的连边，每个1（如果要改）向t连边。总和减最小割。但是这样无法考虑1和0。考虑使得1和0不能同时选（也不能同时不选），于是不能都不割，也不能都割，所以把是1和是0作为两个点，使他们在一个路径上。这样无法表示不满足某个限制。 想不粗来了qwq 于是注意到我们有一些条件没有用：每个限制一定是某些全是1/全是0，于是其实限制是两类 那么把变量放中间，希望是1的限制放在上面连s，希望是0的放下面连t，每个和他所限制的变量连边，这样可以保证每个点所构成的通路一定是一边（上边/下边）都被割了，这样可以表示最终是1/0 现在最后考虑改变变量的代价：假设这个变量最开始是1，那么我们希望这个代价是加在他不是1上的，就是加在他割去表示1那边的时候。那么我们让他割去1之后仍然联通，于是把他跟1那边的虚拟点联通（1的话就是s）。 于是我们解决了这个问题总结
此题解法可以类比如何使得两个东西不能同时选，不能同时不选
注意观察题目是否有隐藏性质没有使用代码
#include#include #include #include #include #include #include #include #define MAXN 10050#define INF (1<<28)using namespace std;int s, t, n, m, g, sex[MAXN], v[MAXN], ans, level[MAXN<<3], q[MAXN<<3], cnt;struct node{ int v, c; node *next, *rev;}pool[MAXN<<6], *h[MAXN<<4], *cur[MAXN<<4];inline void addedge(int u, int v, int c){ node *p1 = &pool[cnt++], *p2 = &pool[cnt++]; *p1 = node{v, c, h[u], p2}, h[u] = p1; *p2 = node{u, 0, h[v], p1}, h[v] = p2;}// s 0 t 1bool bfs(){ int front = 0, rear = 1; memset(level, 0, sizeof(level)); level[s] = 1; q[0] = s; while(front < rear){ int u = q[front++]; if(u == t) return 1; for(node *p = h[u]; p; p = p->next){ if(!level[p->v] && p->c){ q[rear++] = p->v; level[p->v] = level[u]+1; } } } return 0;}int dfs(int u, int t, int f){ if(u == t) return f; int flow = 0, F, Min; for(node *&p = cur[u]; p; p = p->next){ if(level[p->v] == level[u]+1 && p->c){ Min = min(f-flow, p->c); F = dfs(p->v, t, Min); flow += F; p->c -= F; p->rev->c += F; if(flow == f) return flow; } } return flow;}int Dinic(){ int ret = 0; while(bfs()){ for(int i = s; i <= t; i++) cur[i] = h[i]; ret += dfs(s, t, INF); } return ret;}int main(){ scanf("%d%d%d", &n, &m, &g); t = n+m+1; int w, k, exp, fri, cur; for(int i = 1; i <= n; i++) scanf("%d", &sex[i]); for(int i = 1; i <= n; i++) scanf("%d", &v[i]); for(int i = 1; i <= m; i++) { scanf("%d%d%d", &exp, &w, &k); ans += w; for(int j = 1; j <= k; j++) { scanf("%d", &cur); if(exp) addedge(cur+m, i, INF); else addedge(i, cur+m, INF); } scanf("%d", &fri); w += g*fri; if(exp) addedge(i, t, w); else addedge(s, i, w); } for(int i = 1; i <= n; i++) { if(sex[i]) addedge(i+m, t, v[i]); else addedge(s, i+m, v[i]); } int cut = Dinic(); //cout< <<' '; ans -= cut; printf("%d", ans); return 0;}