CF 103E Buying Sets 最大权闭合子图,匹配 难度:4

http://codeforces.com/problemset/problem/103/E

这道题首先一看就很像是最大权闭合子图,但是我们可以认为现在有两种点,数字和集合点,我们需要消除数字点的影响才能直接运用最大权闭合子图.

进行二分匹配,使得每个集合都唯一匹配一个数字,买下一个集合点,则意味着该集合中所有数字的对应匹配集合点都要被买下,也就是可以建立一个新图,其中某个集合点向对应数字代表的集合点连单向边,可以证明对于任意权闭合子图中的集合点,集合中所有数字的对应匹配集合点都已经在这个权闭合子图中.对这个新图的所有价格取反,答案即最大权的负数

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=305;
const int maxm=2*maxn+maxn*maxn;
const int sups=303,supt=304;
const int inf=0x6ffffff;

int n;//original aspects
int price[maxn];
int st[maxn][maxn],nst[maxn];

int mch[2*maxn];//Match
bool vis[2*maxn];

int first[maxn],elen;//maximum flow
struct edge{
    int nxt,f,t,c;
}e[maxm];
int dis[maxn],gap[maxn];

bool subMatch(int s){
    vis[s]=true;
    for(int j=0;j<nst[s];j++){
        int t=st[s][j]+n;
        if(vis[t]||mch[t]==s)continue;
        if(mch[t]==0||(!vis[mch[t]]&&subMatch(mch[t]))){
            mch[t]=s;
            mch[s]=t;
            return true;
        }
    }
    return false;
}
void Match(){
    for(int i=1;i<=n;i++){
        if(mch[i]==0){
            memset(vis,false,sizeof(vis));
            subMatch(i);
        }
    }
}

void addedge(int f,int t,int c){
    e[elen].nxt=first[f];
    e[elen].f=f;
    e[elen].t=t;
    e[elen].c=c;
    first[f]=elen++;
}
void build(){
    for(int i=1;i<=n;i++){
        if(price[i]>=0){
            addedge(sups,i,price[i]);
            addedge(i,sups,0);
        }
        else {
            addedge(i,supt,-price[i]);
            addedge(supt,i,0);
        }
        for(int j=0;j<nst[i];j++){
            int t=mch[st[i][j]+n];
            addedge(i,t,inf);
            addedge(t,i,0);
        }
    }
}
int dfs(int s,int flow){
    if(s==supt)return flow;
    int mindis=n;
    int tflow=flow,sub;
    for(int p=first[s];p!=-1;p=e[p].nxt){
        int t=e[p].t;
        if(e[p].c>0){
            if(dis[t]+1==dis[s]){
                sub=dfs(t,min(tflow,e[p].c));
                e[p].c-=sub;e[p^1].c+=sub;
                tflow-=sub;
                if(dis[sups]>n)return flow-tflow;
                if(tflow<=0)break;
            }
            mindis=min(mindis,dis[t]);
        }
    }
    if(flow==tflow){
        --gap[dis[s]];
        if(gap[dis[s]]==0)dis[sups]=n+1;
        else{
            dis[s]=mindis+1;
            ++gap[dis[s]];
        }
    }
    return flow-tflow;
}
int maxflow(){
    int flow=0;
    gap[0]=n+2;
    while(dis[sups]<=n){
        flow+=dfs(sups,inf);
    }
    return flow;
}

int main(){
    int ans=0;
    memset(first,-1,sizeof(first));
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",nst+i);
        for(int j=0;j<nst[i];j++){
            scanf("%d",st[i]+j);
        }
    }
    for(int i=1;i<=n;i++){
        scanf("%d",price+i);
        price[i]*=-1;
        if(price[i]>=0)ans+=price[i];
    }

    Match();
    build();
    ans=maxflow()-ans;
    printf("%d
",ans);
    return 0;
}