沙发

用户名：admin12

访问量：4003

签　名：

看不见我~~看不见我~

等　　级
排　　名	613
经　　验	4161
参赛次数	1
文章发表	5
年　　龄	15
在职情况	学生
学　　校
专　　业

　　自我简介：

小蒟蒻一只，膜拜大佬

TA的其他文章

蓝桥杯算法训练VIP-Entertaining Geodetics-题解(C++代码)
浏览：481

你可能喜欢

A+B for Input-Output Practice (II) （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C++代码）为什么回车不算字符

蓝桥杯算法训练VIP-Buying Sets-题解(C++代码)

　　作者: 沙发　　　　发表时间：2020-04-04 11:18:14 浏览：483　|　评论：0　

原题链接：蓝桥杯算法训练VIP-Buying Sets

闭合图:对于一个有向图G，存在点集合V，任取点u属于V，u的出边的另一个点也属于V，则为闭合图。
            任取一起点，终点必定是无出度的点。
最大权闭合子图：当每个点有一个权值w（有正有负），点权和最大的闭合图为最大权闭合子图。

求最大权闭合子图:这个问题可以转化为最小割问题，用网络流解决。从源点s向每个正权点连一条容量为权值的边，每个负  权点向汇点t连一条容量为权值的绝对值的边，有向图原来的边容量全部为无限大。求它的最小割，割掉后，与源点s仍连通的点构成最大权闭合子图(s-t割中的s集合)，最大权值为正权值之和-最小割,注意在数值上,最大流和最小割是相等的,所以建立图后求最大流即可.

题目分析:题目中说任选k个集合的并集的势(元素个数)一定大于等于k,又任意元素都是大于等于1并小于等于n.若选所有n个集合的并集的势一定等于n,可以发现集合和元素是完美匹配的,即把集合标号与元素 作为一张二分图,一定存在一个完美匹配.一个集合对应一个元素,选取一个集合则其中的元素对应的集合也必须选取,则问题就变成了最小权闭合子图,可以把权值取反,正权点当做负权点,负权点当做正权点,套上最大权模板来做 ,求出最大权值后取相反数就是答案.
```cpp

#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;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

沙发

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言训练-最大数问题（C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C++代码）为什么回车不算字符

蓝桥杯算法训练VIP-Buying Sets-题解(C++代码)

评论区

精彩推荐

小明A+B （C语言代码）

C语言考试练习题_排列（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

【计算两点间的距离】（C语言代码）

打印十字图（C语言代码）

演讲大赛评分（C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

沙发

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言训练-最大数问题 （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C++代码）为什么回车不算字符

蓝桥杯算法训练VIP-Buying Sets-题解(C++代码)

评论区

精彩推荐

小明A+B （C语言代码）

C语言考试练习题_排列 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

【计算两点间的距离】 （C语言代码）

打印十字图 （C语言代码）

演讲大赛评分 （C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言训练-最大数问题（C语言代码）

　　评论区

C语言考试练习题_排列（C语言代码）

【计算两点间的距离】（C语言代码）

打印十字图（C语言代码）

演讲大赛评分（C语言代码）