- 思维有些江化了,一上来就想费用流做法,但其实就是个最小割啊.
- 考虑先将所有的收益拿到,再减去不能拿的以及三元组 ((i,j,k)) 产生的代价.即,先让 (ans=sum a_i+b_i+sum_{(S,a,b)} b).
- 然后要让减去的最小,尝试构造一个最小割模型.建一个源点 (S) ,一个汇点 (T) .
- 为了满足每个点只能选一种动物,从 (S) 向每个点 (i) 连权值为 (a_i) 的边,从每个点 (i) 向 (T) 连权值为 (b_i) 的边.
- 为了处理三元组 ((i,j,k)) ,对每个这样的三元组,在 (i o j,j o i) 都连一条权值为 (k) 的边.这样只要两者割的不一样,就还需要割掉中间的这条边.
- 为了处理三元组 ((S,a,b)) ,新建一个点 (np) ,若 (a=0) , 就从 (S) 向 (np) 连一条权值为 (b) 的边,从 (np) 向 (forall iin S) 连一条权值为 (inf) 的边.这样要么割掉这个收益 (b) ,要么就全部割羊的边,即全选牛.
- (a=1) 同理,从 (np) 向 (T) 连一条权值为 (b) 的边,从 (forall iin S) 向 (np) 连一条权值为 (inf) 的边.
- 建出图后跑一跑最小割,用 (ans) 减去它即得答案.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 1e18
inline ll read()
{
ll out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
fh=-1,jp=getchar();
while (jp>='0'&&jp<='9')
out=out*10+jp-'0',jp=getchar();
return out*fh;
}
const int MAXN=1e6+10;
int cnt=-1,head[MAXN],nx[MAXN],to[MAXN];
ll flow[MAXN];
void addedge(int u,int v,ll Flow)
{
++cnt;
to[cnt]=v;
nx[cnt]=head[u];
flow[cnt]=Flow;
head[u]=cnt;
}
void ins(int u,int v,ll Flow)
{
addedge(u,v,Flow);
addedge(v,u,0);
}
int tot=0;
int cur[MAXN],dep[MAXN];
ll maxflow=0;
bool bfs(int S,int T)
{
for(int i=1;i<=tot;++i)
dep[i]=-1;
for(int i=1;i<=tot;++i)
cur[i]=head[i];
dep[S]=0;
queue<int> q;
q.push(S);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=nx[i])
{
int v=to[i];
if(flow[i] && dep[v]==-1)
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
if(dep[T]==-1)
return false;
return true;
}
ll dfs(int u,int t,ll limit)
{
if(!limit || u==t)
return limit;
ll Flow=0,f;
for(int i=cur[u];i!=-1;i=nx[i])
{
cur[u]=i;
int v=to[i];
if(dep[v]==dep[u]+1 && (f=dfs(v,t,min(limit,flow[i]))))
{
Flow+=f;
limit-=f;
flow[i]-=f;
flow[i^1]+=f;
if(!limit)
break;
}
}
return Flow;
}
void Dinic(int S,int T)
{
while(bfs(S,T))
maxflow+=dfs(S,T,inf);
}
int n,m,k;
int field[MAXN];
int main()
{
freopen("work.in","r",stdin);
freopen("work.out","w",stdout);
memset(head,-1,sizeof head);
int S=++tot;
int T=++tot;
n=read(),m=read(),k=read();
ll ans=0;
for(int i=1;i<=n;++i)
{
field[i]=++tot;
ll a=read();
ins(S,field[i],a);
ans+=a;
}
for(int i=1;i<=n;++i)
{
ll b=read();
ins(field[i],T,b);
ans+=b;
}
while(m--)
{
int i=read(),j=read();
ll w=read();
ins(field[i],field[j],w);
ins(field[j],field[i],w);
}
while(k--)
{
int t=read(),a=read();
ll b=read();
ans+=b;
int np=++tot;
if(a==0)
{
ins(S,np,b);
for(int i=1;i<=t;++i)
{
int x=read();
ins(np,field[x],inf);
}
}
else
{
ins(np,T,b);
for(int i=1;i<=t;++i)
{
int x=read();
ins(field[x],np,inf);
}
}
}
Dinic(S,T);
ans-=maxflow;
cout<<ans<<endl;
return 0;
}