codeforces311E.Biologist(最大权闭合子图)

题目链接:codeforces311E.Biologist

题意:

有n个点,每个点的颜色为黑或白,可以花vi的代价来更改第i个点的颜色。

有m个条件,要求一个集合内所有点的颜色都是某种颜色,若满足能得到相应的收益,没满足则付出相应的代价。

问最大收益。

题解:

网络流最大权闭合子图模型,转化为最小损失来做。

重点在建图:

  1. 对于原本是0的点连边(S,i,vi);对于原本是1的点连边(i,T,vi)。
  2. 对于要求全是0的点,集合中所有元素连边(i+n,x,inf),然后连边(S,i+n,wi)。
  3. 对于要求全是1的点,集合中所有元素连边(x,i+n,inf),然后连边(i+n,T,wi)。
  4. 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;
}

发表留言

人生在世,错别字在所难免,无需纠正。