dinic+当前弧优化
只有#1和#2AC,剩下都是RE
用test函数检查过,认为建图没问题
私货注意
#include <bits/stdc++.h>
#define f(i,a,b) for (int i=a;i<=b;++i)
#define buildBoth(x,y,z) build(x,y,z),build(y,x,0)
#define ll long long
#define Reimu cout<<"=Net Graph incident="<<'\n'
const signed N=5e5+5;
const signed M=1e5+5;
const ll Miku=LONG_LONG_MAX;
using namespace std;
struct Edge{
int nxt,to;
ll val;
}sav[N];
int head[M],tot=1,n;
int now[M];// 对于节点i的最后一次访问边的编号
int S,T;// 源点,汇点
ll dis[M],ans;
int type,comb;
ll alladd;
void build(int x,int y,ll z){
tot++;
sav[tot].nxt=head[x];
sav[tot].to=y;
sav[tot].val=z;
head[x]=tot;
}
bool bfs(){
f(i,1,n)
dis[i]=-Miku;
queue<int> q;
q.push(S);
dis[S]=1;
now[S]=head[S];
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=sav[i].nxt){
if(sav[i].val==0)
continue;
int v=sav[i].to;
if(dis[v]==-Miku){
dis[v]=dis[u]+1;
q.push(v);
now[v]=head[v];
if(v==T)
return 1;
}
}
}
return 0;
}
ll dfs(int u,ll sum){// sum是整条增广路对最大流的贡献
if(u==T)
return sum;
ll minval=0,res=0;// k是当前最小的剩余容量
for(int i=now[u];i;i=sav[i].nxt){// 剪枝
now[u]=i;// 更新当前弧
if(sav[i].val==0)
continue;
int v=sav[i].to;
if(dis[v]==dis[u]+1){
minval=dfs(v,min(sum,(ll)sav[i].val));
if(minval==0)
dis[v]=-Miku;// 对增广结束的点剪枝
sav[i].val-=minval;
sav[i^1].val+=minval;// 反向边
res+=minval;// 经过该点的所有流量和(流出的总量)
sum-=minval;// 经过该点的剩余流量
}
}
return res;
}
void test(){
cout<<n<<'\n';
// 输出这个图 起点 终点 边权
f(i,1,n){
for(int j=head[i];j;j=sav[j].nxt){
cout<<i<<' '<<sav[j].to<<' '<<sav[j].val<<'\n';
}
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>type;
S=type+1,T=type+2;
n=T;
int tmp;
f(i,1,type){
cin>>tmp;
alladd+=tmp;
buildBoth(S,i,tmp);
}
f(i,1,type){
cin>>tmp;
alladd+=tmp;
buildBoth(i,T,tmp);
}
cin>>comb;
int a,b;
f(i,1,comb){
cin>>tmp;
cin>>a>>b;
alladd+=a+b;
n+=2;
buildBoth(S,n-1,a);
buildBoth(n,T,b);
f(j,1,tmp){
cin>>a;
buildBoth(n-1,a,Miku);
buildBoth(a,n,Miku);
}
}
// test();
while(bfs()){
ans+=dfs(S,Miku);
}
cout<<alladd-ans<<'\n';
return 0;
Reimu;
}