POJ1904 强联通(最大匹配可能性)
最大 匹配 可能性 联通
2023-09-11 14:13:59 时间
题意:
有n个王子,n个公主,然后给你每个王子喜欢的公主,最后问你在不影响最大匹配的前提下,每个王子可以匹配那些公主。
思路:
有n个王子,n个公主,然后给你每个王子喜欢的公主,最后问你在不影响最大匹配的前提下,每个王子可以匹配那些公主。
思路:
是hdu4685的减弱版,之前研究过hdu4685所以这个题目直接水过了,对于这个题目,我们把王子和他喜欢的公主之间建连边,建立一个二分图,然后对于题目给的已经匹配好了的(有的题目没给,直接就自己跑一边二分匹配自己找),之间建立反边,就是建立公主到王子的边,然后一遍强联通,如果同意个分量里的男女可以匹配。这样记录每一个然后sort一下就行了。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
#define N_node 5000
#define N_edge 1000000
using namespace std;
typedef struct
{
int to ,next;
}STAR;
STAR E1[N_edge] ,E2[N_edge];
int list1[N_node] ,list2[N_node] ,tot;
int Belong[N_node] ,cont;
int mark[N_node];
int ans[N_node];
stack<int>st;
void add(int a ,int b)
{
E1[++tot].to = b;
E1[tot].next = list1[a];
list1[a] = tot;
E2[tot].to = a;
E2[tot].next = list2[b];
list2[b] = tot;
}
void DFS1(int s)
{
mark[s] = 1;
for(int k = list1[s] ;k ;k = E1[k].next)
{
int to = E1[k].to;
if(!mark[to]) DFS1(to);
}
st.push(s);
}
void DFS2(int s)
{
mark[s] = 1;
Belong[s] = cont;
for(int k = list2[s] ;k ;k = E2[k].next)
{
int to = E2[k].to;
if(!mark[to]) DFS2(to);
}
}
int main ()
{
int n ,i ,j ,a ,nn;
while(~scanf("%d" ,&n))
{
memset(list1 ,0 ,sizeof(list1));
memset(list2 ,0 ,sizeof(list2));
tot = 1;
for(i = 1 ;i <= n ;i ++)
{
scanf("%d" ,&nn);
for(j = 1 ;j <= nn ;j ++)
{
scanf("%d" ,&a);
add(i ,a + n);
}
}
for(i = 1 ;i <= n ;i ++)
{
scanf("%d" ,&a);
add(a + n ,i);
}
memset(mark ,0 ,sizeof(mark));
while(!st.empty()) st.pop();
for(i = 1 ;i <= n + n ;i ++)
{
if(!mark[i]) DFS1(i);
}
memset(mark ,0 ,sizeof(mark));
cont = 0;
while(!st.empty())
{
int to = st.top();
st.pop();
if(!mark[to])
{
cont ++;
DFS2(to);
}
}
for(i = 1 ;i <= n ;i ++)
{
int tt = 0;
for(int k = list1[i] ;k ;k = E1[k].next)
{
int to = E1[k].to;
if(Belong[i] == Belong[to])
ans[++tt] = to - n;
}
sort(ans + 1 ,ans + tt + 1);
printf("%d" ,tt);
for(j = 1 ;j <= tt ;j ++)
printf(" %d" ,ans[j]);
puts("");
}
}
return 0;
}
相关文章
- hdu4280 最大流DINIC
- hdu1686 最大匹配次数 KMP
- hdu4685 最大匹配可能性
- hdu4685 最大匹配可能性
- NYOJ239 月老的难题 【二分图最大匹配·匈牙利】
- 【BZOJ1930】[Shoi2003]pacman 吃豆豆 最大费用最大流
- 【BZOJ3261】最大异或和 Trie树+贪心
- 基于最小二乘法和最大似然估计法的系统参数辨识MATLAB仿真
- KMP算法预备知识:字符串match的每一个位置i之前的字符串,前缀与后缀匹配的最大长度是多少
- 匈牙利算法,二分图的最大匹配
- [数据结构]最大流之Ford-Fulkerson算法
- [LeetCode]104. 二叉树的最大深度
- [LeetCode]1422.分割字符串的最大得分
- 动态规划解决最大乘积系列问题(碾压暴力枚举)java
- 102、【树与二叉树】leetcode ——654. 最大二叉树(C++版本)
- 中国字实现——最大双向匹配
- hdu 1083 Courses (最大匹配)
- nyoj 44-子串和(子串和最大问题)
- 最大面额钞票10的21次方
- 智能家居的最大问题:我们真的需要物联网吗?
- 【bzoj2044】三维导弹拦截 dp+二分图最大匹配
- 【bzoj1059】[ZJOI2007]矩阵游戏 二分图最大匹配
- 算法训练 最大最小公倍数(数论)