@[尤佳骏](/space/show?uid=110713) 为什么七班的都会网络流了
by YellowBean_Elsa @ 2019-08-11 15:49:28
my code
```cpp
#include<bits/stdc++.h>
using namespace std;
const int inf=(1<<29);
inline int read(){
int x=0;char c=getchar();
while(c>'9' || c<'0')c=getchar();
while(c<='9' && c>='0')x=(x<<1)+(x<<3)+c-'0',c=getchar();
return x;
}
int n,m,a[1005],b[1005];
int k,c1,c2,p,s,t,sum;
int v[4000010],w[4000010],next[4000010],first[4000010],d[4000010],tot=1;
queue<int> q;
bool bfs(){
while(q.size())q.pop();
memset(d,0,sizeof(d));
q.push(s);d[s]=1;
while(q.size()){
int x=q.front();q.pop();
for(int i=first[x];i;i=next[i]){
int y=v[i];
if(!w[i] || d[y])continue;
d[y]=d[x]+1;
q.push(y);
if(y==t)return 1;
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t)return flow;
int rest=flow,y,k;
for(int i=first[x];i&&rest;i=next[i]){
int y=v[i];
if(!w[i] || d[y]!=d[x]+1)continue;
k=dinic(y,min(w[i],rest));
if(!k)d[y]=0;
w[i]-=k;w[i^1]+=k;
rest-=k;
}
return flow-rest;
}
inline void add(int x,int y,int z){
v[++tot]=y;w[tot]=z;
next[tot]=first[x];
first[x]=tot;
}
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)b[i]=read();
m=read();
t=n+m*2+1,s=0;
for(int i=1;i<=n;i++){
add(i,s,0);add(s,i,a[i]);
add(i,t,b[i]);add(t,i,0);
}
for(int i=1;i<=m;i++){
k=read();c1=read();c2=read();
sum+=c1+c2;
int x=n+i*2-1,y=n+i*2;
add(s,x,c1);add(x,s,0);
add(y,t,c2);add(t,y,0);
for(int j=1;j<=k;j++){
p=read();
add(x,p,inf);add(p,x,0);
add(p,y,inf);add(y,p,0);
}
}
int ans=0,flow=0;
while(bfs())
while(flow=dinic(s,inf))ans+=flow;
for(int i=1;i<=n;i++)
sum+=a[i]+b[i];
printf("%d\n",sum-ans);
return 0;
}
```
张逸铭你自己看吧
qianzhenyang loves tangyinuo
by YellowBean_Elsa @ 2019-08-11 15:54:35
kaogu
by TensorFlow_js @ 2020-07-02 15:34:02