蓝桥杯 buying sets求闭合子图最小,最大权
题目:
给定n个集合, 要求选出其中某些集合, 使得这些集合的并集的势, 等于选出的集合的数目.对于任意的k(1<=k<=n), 满从中选出任意k个集合, 这k个集合的并集的势一定大于等于k.每个集合有一个权值, 每个选择方案的代价是所选的集合的权值的和.请输出代价最小的选择方案的代价.当然, 不选择任何一个集合是一个可行的方案(权值和为0), 但不一定最优(权值和可以为负).
第一行一个正整数n(1<=n<=300), 为集合个数.
在接下来n行中, 第i行描述第i个集合:
首先给出一个正整数m[i]为该集合的势, 显然1<=m[i]<=n.
接下来m[i]个在1到n之间的整数, 表示该集合中的元素.
最后一行n个整数, 为每个集合的权值, 绝对值不超过1e6.
分析:
闭合图:对于一个有向图G，存在点集合V，任取点u属于V，u的出边的另一个点也属于V，则为闭合图。
任取一起点，终点必定是无出度的点。
最大权闭合子图：当每个点有一个权值w（有正有负），点权和最大的闭合图为最大权闭合子图。求最大权闭合子图:这个问题可以转化为最小割问题，用网络流解决。从源点s向每个正权点连一条容量为权值的边，每个负 权点向汇点t连一条容量为权值的绝对值的边，有向图原来的边容量全部为无限大。求它的最小割，割掉后，与源点s仍连通的点构成最大权闭合子图(s-t割中的s集合)，最大权值为正权值之和-最小割,注意在数值上,最大流和最小割是相等的,所以建立图后求最大流即可.
题目分析:题目中说任选k个集合的并集的势(元素个数)一定大于等于k,又任意元素都是大于等于1并小于等于n.若选所有n个集合的并集的势一定等于n,可以发现集合和元素是完美匹配的,即把集合标号与元素 作为一张二分图,一定存在一个完美匹配.一个集合对应一个元素,选取一个集合则其中的元素对应的集合也必须选取,则问题就变成了最小权闭合子图,可以把权值取反,正权点当做负权点,负权点当做正权点,套上最大权模板来做 ,求出最大权值后取相反数就是答案.
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
const int MAXN=305;
const int INF=1<<30;
int setnum;
vector<int> sets[MAXN];
int weight[MAXN];
int match[MAXN];
int visited[MAXN];
int posweight=0;
struct Edge{
int from,to,cap,flow;
};
vector<int> G[MAXN];
vector<Edge> edges;
int deep[MAXN];
bool dfs(int u){
for(int i=0;i<sets[u].size();i++){
int v=sets[u][i];
if(visited[v])continue;
visited[v]=1;
if(!match[v]||dfs(match[v])){
match[v]=u;
return true;
}
}
return false;
}
void hungary(){//匈牙利算法找到完美匹配
memset(match,0,sizeof(match));
for(int i=1;i<=setnum;i++){
memset(visited,0,sizeof(visited));
dfs(i);
}
}
void addedge(int u,int v,int cap){
edges.push_back(Edge{u,v,cap,0});
edges.push_back(Edge{v,u,0,0});
int m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
void init(){//根据匈牙利算法找到的完美匹配建立搜索图,0为源点,setnum+1为汇点
hungary();
for(int i=1;i<=setnum;i++)
if(weight[i]<0){addedge(0,i,-weight[i]);posweight-=weight[i];}//权值取反,负权点当正权点,正权点当负权点
else addedge(i,setnum+1,weight[i]);
for(int i=1;i<=setnum;i++){
for(int j=0;j<sets[i].size();j++){
int v=sets[i][j];//取出相应集合中的元素
if(match[v]!=i)addedge(i,match[v],INF);
}
}
}
bool bfs(){//bfs分层次图
memset(deep,0,sizeof(deep));
queue<int> Q;
Q.push(0);//入队源点
deep[0]=1;
while(!Q.empty()){
int u=Q.front();
Q.pop();
for(int i=0;i<G[u].size();i++){
Edge edge=edges[G[u][i]];
if(!deep[edge.to]&&edge.cap>edge.flow){
deep[edge.to]=deep[edge.from]+1;
Q.push(edge.to);
}
}
}
return deep[setnum+1];
}
int dinc(int u,int pref){//dinc求最小割即最大流
if(u==setnum+1)return pref;//找到源点
int f=0;
for(int i=0;i<G[u].size();i++){
int t=G[u][i];
Edge edge=edges[t];
if(edge.cap>edge.flow&&deep[edge.from]==deep[edge.to]-1){//有残量可以增广并且深度符合
int temp=min(pref,edge.cap-edge.flow);
int x=dinc(edge.to,temp);
edges[t].flow+=x;
edges[t^1].flow-=x;
f+=x;
pref-=x;
}
}
return f;
}
int solve(){//求闭合图最大权值
init();
int maxflow=0;
while(bfs()){
maxflow+=dinc(0,1<<30);
}
return posweight-maxflow;
}
int main(){
cin>>setnum;
int k,ele;
for(int i=1;i<=setnum;i++){
cin>>k;
for(int j=0;j<k;j++){
cin>>ele;
sets[i].push_back(ele);
}
}
for(int i=1;i<=setnum;i++)
cin>>weight[i];
int ans=-solve();//因为权值取反了,最小权值就是最大权值的相反数
if(ans>0)cout<<0<<endl;
else cout<<ans<<endl;
return 0;
}