题意:
有n个点,每个点的颜色为黑或白,可以花vi的代价来更改第i个点的颜色。
有m个条件,要求一个集合内所有点的颜色都是某种颜色,若满足能得到相应的收益,没满足则付出相应的代价。
问最大收益。
题解:
网络流最大权闭合子图模型,转化为最小损失来做。
重点在建图:
- 对于原本是0的点连边(S,i,vi);对于原本是1的点连边(i,T,vi)。
- 对于要求全是0的点,集合中所有元素连边(i+n,x,inf),然后连边(S,i+n,wi)。
- 对于要求全是1的点,集合中所有元素连边(x,i+n,inf),然后连边(i+n,T,wi)。
- g的损失直接加在wi中。
参考代码:
#include<bits/stdc++.h>
using namespace std;
const int inf=0x7ffffff;
const int MAXN=2e4;
const int MAXM=1e7;
struct node
{
int v,w,nxt;
} edge[MAXM*2];
int n,m,g,cnt=0,st,ed;
int a[10009],b[10009];
int fir[MAXN],depth[MAXN],cur[MAXN];
void addedge(int u,int v,int w)
{
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].nxt=fir[u];
fir[u]=cnt++;
}
int dfs(int u,int flow)
{
if(u==ed)
return flow;
for(int& i=cur[u]; i!=-1; i=edge[i].nxt)
{
int v=edge[i].v;
int w=edge[i].w;
if(depth[v]==depth[u]+1&&w!=0)
{
int di=dfs(v,min(flow,w));
if(di>0)
{
edge[i].w-=di;
edge[i^1].w+=di;
return di;
}
}
}
return 0;
}
bool bfs()
{
queue<int> q;
while(!q.empty())
q.pop();
memset(depth,0,sizeof(depth));
depth[st]=1;
q.push(st);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=fir[u]; i!=-1; i=edge[i].nxt)
{
int v=edge[i].v;
int w=edge[i].w;
if(depth[v]==0&&w>0)
{
depth[v]=depth[u]+1;
q.push(v);
}
}
}
if(depth[ed]>0)
return 1;
else
return 0;
}
int dinic()
{
int tot=0;
while(bfs())
{
for(int i=0; i<=n+m+1; i++)
cur[i]=fir[i];
while(int temp=dfs(st,inf))
tot+=temp;
}
return tot;
}
int main()
{
scanf("%d%d%d",&n,&m,&g);
memset(fir,-1,sizeof(fir));
st=0;
ed=n+m+1;
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
for(int i=1; i<=n; i++)
scanf("%d",&b[i]);
for(int i=1; i<=n; i++)
if(a[i])
addedge(i,ed,b[i]),addedge(ed,i,0);
else
addedge(st,i,b[i]),addedge(i,st,0);
int sum=0;
for(int i=1; i<=m; i++)
{
int f1,w,num,f2;
vector<int> v;
v.clear();
scanf("%d%d%d",&f1,&w,&num);
sum+=w;
int temp;
for(int i=1; i<=num; i++)
{
scanf("%d",&temp);
v.push_back(temp);
}
scanf("%d",&f2);
if(f1)
{
addedge(i+n,ed,w+f2*g);
addedge(ed,i+n,0);
for(int j=0; j<v.size(); j++)
addedge(v[j],i+n,inf),addedge(i+n,v[j],0);
}
else
{
addedge(st,i+n,w+f2*g);
addedge(i+n,st,0);
for(int j=0; j<v.size(); j++)
addedge(i+n,v[j],inf),addedge(v[j],i+n,0);
}
}
int ans=sum-dinic();
printf("%d\n",ans);
return 0;
}