题目链接：
太水了啦 直接最大流跑输出即可。 代码如下：#include#include #include #include #include #include #define MAXN 100010using namespace std;struct Edge{int nxt,to;long long dis;}edge[MAXN<<2];int head[MAXN<<1],dep[MAXN<<1],cur[MAXN<<1],c[MAXN<<1];int n,m,s,t,edge_number=1;long long tot=0;inline void add(int from,int to,long long dis){ edge[++edge_number].dis=dis; edge[edge_number].nxt=head[from]; edge[edge_number].to=to; head[from]=edge_number;}inline bool bfs(int s,int t){ queue q; memset(dep,0x3f,sizeof(dep)); memcpy(cur,head,sizeof(head)); q.push(s); dep[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=edge[i].nxt) { int v=edge[i].to; if(dep[v]==0x3f3f3f3f&&edge[i].dis) { dep[v]=dep[u]+1; q.push(v); } } } if(dep[t]==0x3f3f3f3f) return false; return true;}inline long long dfs(int now,int t,long long minn){ if(now==t||minn==0) return minn; long long flow=0,f; for(int i=cur[now];i;i=edge[i].nxt) { int v=edge[i].to; cur[now]=i; if(dep[v]==dep[now]+1&&(f=dfs(v,t,min(minn,edge[i].dis)))) { flow+=f; minn-=f; edge[i].dis-=f; edge[i^1].dis+=f; if(!minn) break; } } return flow;}inline long long dinic(int s,int t){ long long ans=0; while(bfs(s,t)) ans+=dfs(s,t,(long long)1e18); return ans;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&c[i]),tot+=c[i]; for(int i=1;i<=m;i++) { int p; scanf("%d",&p); for(int j=1;j<=p;j++) { int cur; scanf("%d",&cur); add(i,cur+m,1); add(cur+m,i,0); } } for(int i=1;i<=m;i++) add(0,i,1),add(i,0,0); for(int i=1;i<=n;i++) add(m+i,n+m+1,c[i]),add(n+m+1,m+i,0); if(dinic(0,n+m+1)