rt,89pts,实在找不出错了,以下代码
#include <bits/stdc++.h>
#define inf INT_MAX
using namespace std;
inline long long read() {
long long x;bool f;char ch;
for(f=0;!isdigit(ch=getchar());f=ch=='-');
for(x=ch-48;isdigit(ch=getchar());x=x*10+ch-48);
return f?-x:x;
}
inline void print(long long x,char las) {
if(!x) {
putchar(48),putchar(las);
return ;
}
if(x<0) putchar('-'),x=-x;
int ls[20],k=0;
while(x) ls[++k]=x%10,x/=10;
while(k) putchar(ls[k--]+48);
putchar(las);
return ;
}
struct edge {
int to,name;long long lim;
edge *next;
};
struct graph {
int rs;edge rd[2000002],*head[3002];
inline void add(int u,int v,long long lim) {
rd[rs].to=v;rd[rs].lim=lim;rd[rs].name=rs;rd[rs].next=head[u];head[u]=&rd[rs++];
}
}g1,g2;
int dist[3002],cnt[3022];
int n=read(),s,t;
inline void st() {
queue<int>que;que.push(t);
for(int i=0;i<=n;i++) dist[i]=-1;
dist[t]=0;
cnt[0]=1;
while(!que.empty()) {
int now=que.front();que.pop();
for(edge *i=g2.head[now];i;i=i->next) {
int nex=i->to;
if(dist[nex]==-1) dist[nex]=dist[now]+1,que.push(nex),cnt[dist[nex]]++;
}
}
return ;
}
long long ans=0;
inline long long ISAP(int x,long long lim) {
if(x==t) {
ans-=lim;
return lim;
}
long long used=0;
for(edge *i=g1.head[x];i;i=i->next) {
int nex=i->to;
if(i->lim && dist[x]==dist[nex]+1) {
long long cost=ISAP(nex,min(i->lim,lim-used));
if(cost) {
i->lim-=cost;
g2.rd[i->name].lim+=cost;
used+=cost;
if(used==lim) return used;
}
}
}
for(edge *i=g2.head[x];i;i=i->next) {
int nex=i->to;
if(i->lim && dist[x]==dist[nex]+1) {
long long cost=ISAP(nex,min(i->lim,lim-used));
if(cost) {
i->lim-=cost;
g1.rd[i->name].lim+=cost;
used+=cost;
if(used==lim) return used;
}
}
}
cnt[dist[x]]--;
if(!cnt[dist[x]]) dist[s]=n+1;
dist[x]++;
cnt[dist[x]]++;
return used;
}
int main() {
s=0;t=1;
for(int i=1;i<=n;i++) {
int a=read();ans+=a;
g1.add(s,i+1,a),g2.add(i+1,s,0);
}
for(int i=1;i<=n;i++) {
int a=read();ans+=a;
g1.add(i+1,t,a),g2.add(t,i+1,0);
}
int m=read();
n+=1;
for(int i=1;i<=m;i++) {
int k=read(),c=read();ans+=c;
g1.add(s,n+1,c),g2.add(n+1,s,0);c=read();
g1.add(n+2,t,c),g2.add(t,n+2,0);ans+=c;
while(k--) {
c=read();
g1.add(n+1,c+1,inf),g2.add(c+1,n+1,0);
g2.add(c+1,n+2,inf),g2.add(n+2,c+1,0);
}
n+=2;
}
st();
while(dist[s]<n) ISAP(s,inf);
print(ans,'\n');
return 0;
}