C++(g++ 7.5.0) 解法, 执行用时: 12ms, 内存消耗: 1272K, 提交时间: 2022-09-24 02:35:35

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, M = 210000;
const int INF = 0x3f3f3f3f;

int e[M], ne[M], f[M], h[N], idx;
int cur[N], d[N], q[N];
int n, m, S, T;
int w[1010], last[1010];

void insert(int u, int v, int d) {
    e[idx] = v, ne[idx] = h[u], f[idx] = d, h[u] = idx++;
    e[idx] = u, ne[idx] = h[v], f[idx] = 0, h[v] = idx++;
}

bool bfs() {
    int tt = -1, hh = 0;
    memset(d, -1, sizeof d);
    q[++tt] = S, cur[S] = h[S], d[S] = 0;
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1 && f[i]) {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if (j == T) return true;
                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        int j = e[i];
        cur[u] = i;
        if (d[j] == d[u] + 1 && f[i]) {
            int t = find(j, min(f[i], limit - flow));
            if (!t) d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic() {
    int r = 0, flow;
    while (bfs()) while (flow = find(S, INF)) r += flow;
    return r;
}

int main() {
    scanf("%d%d", &m, &n);
    S = 0, T = n + 1;
    for (int i = 1; i <= m; i++) scanf("%d", w + i);
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) {
        int a, b, k;
        scanf("%d", &a);
        while (a--) {
            scanf("%d", &k);
            if (last[k]) insert(last[k], i, INF);
            else insert(S, i, w[k]);
            last[k] = i;
        }
        scanf("%d", &b);
        insert(i, T, b);
    }
    printf("%d\n", dinic());
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 13ms, 内存消耗: 1412K, 提交时间: 2022-10-10 21:51:59

#include <bits/stdc++.h>
#define inf 0x7f7f7f7f
#define N 210
using namespace std;
int n,m,k,x,y,s=0,t=101;
struct edg{
	int t,next;
	int w;
}edge[N*10100];
int d[N],q[N],pos[N]; // d[i]是层数，q是手工栈 
int last[1010];
int head[N],cur[N],hcnt=-1;
int ans,siz[1010];
void addedge(int x,int y,int w){
	edge[++hcnt].t=y;
	edge[hcnt].w=w;
	edge[hcnt].next=head[x];
	head[x]=hcnt;
}
bool makelevel(int s,int t){
	memset(d,0,sizeof(d));
	memset(q,0,sizeof(q));
	memcpy(cur,head,sizeof(head));
	d[s]=1;
	int l=0,r=0;
	q[r++]=s;
	while(l<r){
		int x=q[l++];
		if(x==t) return true;
		for(int i=head[x];i!=-1;i=edge[i].next){
			if(d[edge[i].t]==0 && edge[i].w!=0){
				q[r++]=edge[i].t;
				d[edge[i].t]=d[x]+1;
			}
		}
	} 
	return false;
}
int dfs(int x,int flow,int t){
	if(x==t) return flow;
	int sum=0;
	for(int i=cur[x];i!=-1;i=edge[i].next){
		cur[x]=i;
		if(edge[i].w!=0 && d[edge[i].t]==d[x]+1){
			int tmp=dfs(edge[i].t,min(edge[i].w,flow-sum),t);
			edge[i].w-=tmp;
			edge[i^1].w+=tmp;
			sum+=tmp;
			if(sum==flow) return sum;
		}
	}
	return sum;
}
int main(){
	memset(head,-1,sizeof(head));
	scanf("%d%d",&m,&n); 
	for(int i=1;i<=m;i++) scanf("%d",&siz[i]);
	for(int i=1;i<=n;i++){
		scanf("%d",&k);
		int sum=0;
		for(int j=1;j<=k;j++){
			scanf("%d",&x);
			if(last[x]){
				addedge(last[x],i,inf);
				addedge(i,last[x],0);
			}else{
                sum+=siz[x];
			}
			last[x]=i;
		}
		addedge(s,i,sum);
		addedge(i,s,0);
		scanf("%d",&y);
		addedge(i,t,y);
		addedge(t,i,0);
	}
	while(makelevel(s,t)){
		ans+=dfs(s,inf,t);
	}
	printf("%d",ans);
	return 0;
}