【题意】
【分析】
经典的最大权闭合图问题,我们将S与所有权值为正的点连一条容量为其权值的边,将所有权值为负的点与T连一条容量为其权值的绝对值的边,原来的边将其容量定为正无穷
然后跑一遍最大流即可
【代码】
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+5; const int inf=0x3f3f3f3f; int n,m,s,t,cnt=1,head[maxn],p[55],c[55],sum; struct edge { int to,nxt,v; }e[maxn<<1]; void add(int x,int y,int z) { e[++cnt].to=y; e[cnt].nxt=head[x]; e[cnt].v=z; head[x]=cnt; e[++cnt].to=x; e[cnt].nxt=head[y]; e[cnt].v=0; head[y]=cnt; } char tools[maxn]; int maxflow,dep[maxn],cur[maxn],in[maxn]; bool bfs() { for(int i=0;i<=t;i++) dep[i]=inf,cur[i]=head[i],in[i]=0; queue <int> q; q.push(s); dep[s]=0; in[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); in[u]=0; for(int i=head[u];i;i=e[i].nxt) { int to=e[i].to; if(dep[to]==inf && e[i].v) { dep[to]=dep[u]+1; if(!in[to]) { q.push(to); in[to]=1; } } } } return (dep[t]!=inf); } int flag; int dfs(int x,int flow) { if(x==t) { flag=1; maxflow+=flow; return flow; } int used=0; for(int &i=cur[x];i;i=e[i].nxt) { int to=e[i].to; if(e[i].v && dep[to]==dep[x]+1) { int tmp=dfs(to,min(flow-used,e[i].v)); if(tmp) { used+=tmp; e[i].v-=tmp; e[i^1].v+=tmp; if(used==flow) break; } } } return used; } void dinic() { while(bfs()) { flag=1; while(flag) { flag=0; dfs(s,inf); } } } int main() { // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); scanf("%d%d",&n,&m); s=0; t=n+m+1; for(int i=1;i<=n;i++) { scanf("%d",&p[i]); sum+=p[i]; add(s,i,p[i]); memset(tools,0,sizeof(tools)); cin.getline(tools,10000); int ulen=0,tool; while(sscanf(tools+ulen,"%d",&tool)==1) { // need[i][tool]=1; add(i,n+tool,inf); if(!tool) ulen++; else { while(tool) { tool/=10; ulen++; } } ulen++; } } for(int i=1;i<=m;i++) scanf("%d",&c[i]); for(int i=1;i<=m;i++) add(i+n,t,c[i]); dinic(); for(int i=1;i<=n;i++) if(dep[i]!=inf) printf("%d ",i); printf("\n"); for(int i=1;i<=m;i++) if(dep[i+n]!=inf) printf("%d ",i); printf("\n"); printf("%d\n",sum-maxflow); return 0; }