初看還以為是那啥最大閉合子圖，然而只是跑一下網(wǎng)絡(luò)流

#include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int N=1e5+50; const int mod=1e9+7; struct Edge{int from,to,cap,flow;Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){} }; struct Dinic{int s,t;vector<Edge>edges;vector<int> G[N];bool vis[N];int d[N];int cur[N];void init(){for (int i=0;i<=t+1;i++)G[i].clear();edges.clear();}void AddEdge(int from,int to,int cap){edges.push_back(Edge(from,to,cap,0));edges.push_back(Edge(to,from,0,0));int mm=edges.size();G[from].push_back(mm-2);G[to].push_back(mm-1); } bool BFS(){memset(vis,0,sizeof(vis));queue<int>q;q.push(s);d[s]=0;vis[s]=1;while (!q.empty()){int x = q.front();q.pop();for (int i = 0;i<G[x].size();i++){Edge &e = edges[G[x][i]];if (!vis[e.to] && e.cap > e.flow){vis[e.to]=1;d[e.to] = d[x]+1;q.push(e.to);}}}return vis[t];} int DFS(int x,int a){if (x==t||a==0) return a;int flow=0,f;for (int &i=cur[x];i<G[x].size();i++){Edge &e=edges[G[x][i]];if (d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){e.flow+=f;edges[G[x][i]^1].flow-=f; //此處忘記反向容量降低，居然還能過(guò)50%樣例flow+=f;a-=f;if (a==0) break;}}return flow; } int Maxflow(int s,int t){this->s=s;this->t=t;int flow=0;while (BFS()){memset(cur,0,sizeof(cur));flow+=DFS(s,inf);}return flow; } }dc; int main(){int T;scanf("%d",&T);while (T--){int n,m;scanf("%d%d",&n,&m);int s=n+m+1,t=n+m+2;dc.init();int sum=0;for (int i = 1; i <= n; ++i){int x;scanf("%d", &x);sum+=x;dc.AddEdge(i,t,x);}for (int i = n+1; i <= n+m; ++i){int x;scanf("%d", &x);dc.AddEdge(s,i,x);}for (int i = n+1; i <= n+m; ++i){int k;scanf("%d", &k);while(k--){int x;scanf("%d", &x);dc.AddEdge(i,x,inf);}}printf("%d\n", sum-dc.Maxflow(s,t));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的托米去购物的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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