分析后看出是最大权闭合子图，那么答案就是正权值-最大流。
#include <cstdio> #include <queue> #include <vector> #include <string> #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N=2505; const int inf=1<<29; int m,n,sum,s,t; int cur[155]; int head[155]; vector<int> in[155]; struct edge{ int nxt,v,ro,flow; }e[N]; int tot=1; bool fl[155],fk[155]; inline void add(int u,int v,int ro) { e[++tot].v=v; e[tot].ro=ro; e[tot].nxt=head[u]; head[u]=tot; e[++tot].v=u; e[tot].ro=0; e[tot].nxt=head[v]; head[v]=tot; } int dis[155]; bool vis[155]; inline bool bfs(int s,int t) { //memset(dis,-1,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s]=0;vis[s]=1; queue<int >q; q.push(s); while (!q.empty()) { int x=q.front(); q.pop(); for (int i=head[x];i;i=e[i].nxt) { if (!vis[e[i].v]&&e[i].ro>e[i].flow) { q.push(e[i].v); dis[e[i].v]=dis[x]+1; vis[e[i].v]=1; } } } 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;i=e[i].nxt) { if (dis[x]+1==dis[e[i].v]&&((f=dfs(e[i].v,min(a,e[i].ro-e[i].flow)))>0)) { flow+=f; e[i].flow+=f; e[i^1].flow-=f; a-=f; if (a==0) break; } } return flow; } inline int dinic(int s,int t) { int i,flow=0; while (bfs(s,t)) { for (i=0;i<=n+m+1;i++) cur[i]=head[i]; flow+=dfs(s,inf); } return flow; } int main() { register int i,j; scanf("%d %d",&m,&n);char c=getchar ();c=getchar (); s=0,t=n+m+1; for (i=1;i<=m;i++) { int w=0,x; string ch; getline(cin,ch); for (j=0;j<ch.size();j++) { if (ch[j]<'0'||ch[j]>'9') continue; else while (ch[j]>='0'&&ch[j]<='9') { w=w*10+ch[j]-'0';j++; } break; } sum+=w; add(s,i,w); for (j=j;j<ch.size();j++) { if (ch[j]<'0'||ch[j]>'9') { x=0; continue; } else while (ch[j]>='0'&&ch[j]<='9') { x=x*10+ch[j]-'0';j++; } in[i].push_back(x); add(i,m+x,inf);x=0; } } for (i=1;i<=n;i++) { int x; scanf("%d",&x); add(m+i,t,x); } int maf=dinic(s,t); for (i=1;i<=m;i++) { if (vis[i]) { printf("%d ",i); } } printf("\n"); for (i=1;i<=n;i++) if (vis[i+m]) printf("%d ",i); printf("\n%d",sum-maf); return 0; }
