hiho #1127 : 二分图三·二分图最小点覆盖和最大独立集(无向图 二分图匹配)

2024-06-15 19:32

本文主要是介绍hiho #1127 : 二分图三·二分图最小点覆盖和最大独立集(无向图 二分图匹配),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:点击打开链接

#1127 : 二分图三·二分图最小点覆盖和最大独立集

时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB
描述

在上次安排完相亲之后又过了挺长时间,大家好像都差不多见过面了。不过相亲这个事不是说那么容易的,所以Nettle的姑姑打算收集一下之前的情况并再安排一次相亲。所以现在摆在Nettle面前的有2个问题:

1.姑姑想要了解之前所有相亲的情况。对于任一个一次相亲,只要跟参与相亲的两人交流就可以得到这次相亲的情况。如果一个人参加了多次相亲,那么跟他交流就可以知道这几次相亲的情况。那么问题来了,挖掘技术到底哪家强姑姑最少需要跟多少人进行交流可以了解到所有相亲的情况。

问题1解答

2.因为春节快要结束了,姑姑打算给这些人再安排一次集体相亲。集体相亲也就是所有人在一起相亲,不再安排一对一对的进行相亲。但是姑姑有个条件,要求所有参与相亲的人之前都没有见过。也就是说在之前的每一次相亲中的两人不会被同时邀请来参加这次集体相亲。那么问题又来了,姑姑最多可以让多少人参与这个集体相亲。

问题2解答

输入

第1行:2个正整数,N,M(N表示点数 2≤N≤1,000,M表示边数1≤M≤5,000)
第2..M+1行:每行两个整数u,v,表示一条无向边(u,v)

输出

第1行:1个整数,表示最小点覆盖数
第2行:1个整数,表示最大独立集数

样例输入
5 4
3 2
1 3
5 4
1 5
样例输出
2
3

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 10010
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)using namespace std;void read(int &x)
{char ch;x=0;while(ch=getchar(),ch!=' '&&ch!='\n'){x=x*10+ch-'0';}
}int n,m;
int mp[1050][1050];
int link[1050];
int vis[1050];
int ans;bool dfs(int u)
{for(int i=1;i<=n;i++){if(mp[u][i]&&!vis[i]){vis[i]=1;if(link[i]==-1||dfs(link[i])){link[i]=u;return 1;}}}return 0;
}void hungary()
{MEM(link,-1);for(int i=1;i<=n;i++){MEM(vis,0);if(dfs(i))ans++;}
}int main()
{
//    fread;while(scanf("%d%d",&n,&m)!=EOF){MEM(mp,0);while(m--){int u,v;scanf("%d%d",&u,&v);
//            u--; v--;mp[u][v]=mp[v][u]=1;//无向图建图}ans=0;hungary();printf("%d\n",ans/2);//答案除以2  最小点覆盖数=二分图匹配数printf("%d\n",n-ans/2);//最大独立集数=点的个数-二分图匹配数}return 0;
}



这篇关于hiho #1127 : 二分图三·二分图最小点覆盖和最大独立集(无向图 二分图匹配)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1064367

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 1102 uva 10397(最小生成树prim)

hdu 1102: 题意: 给一个邻接矩阵,给一些村庄间已经修的路,问最小生成树。 解析: 把已经修的路的权值改为0,套个prim()。 注意prim 最外层循坏为n-1。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl