加载中…HDU 3836 Equivalent Sets Multi-University_Training_Contest Host_By_HNU
(2011-07-13 11:41:06)
标签：
hdu3836equivalentsets连通it |
分类： 网络流 |
题目描述：
有n个集合，m个关系，每个关系i，j，表示i集合是j集合的子集。
问你最少再添加几个关系，能够让所有的集合都相同。
解题报告：
其实就是再加多少条边，变成一个连通图。
先tarjan缩点后，图上就剩下一些点或者线（1->2 1->3 1->4算作3条线）
发现，只要首尾相连就是最优的方式。
所以，点或者线的数目就是图中max(出度为0的点，入度为0的点）。
就是答案。
代码如下：
dfn[id]
= low[id] = ++index;
instack[id] = 1; sta[top++] = id;
for(int
i = 0; i < v[id].size(); i++)
if (!dfn[v[id][i]])
{
tarjan(v[id][i]);
if (low[v[id][i]] < low[id])
low[id] = low[v[id][i]];
}
else if (instack[v[id][i]]
&& dfn[v[id][i]] <
low[id])
low[id] = dfn[v[id][i]];
if
(dfn[id] == low[id])
{
int tmp;
do
{
tmp = sta[--top]; instack[tmp] = 0;
belong[tmp] = cnt;
num[cnt]++;
}while(tmp != id);
cnt++;
}
memset(num, 0, sizeof(num));
memset(instack, 0, sizeof(instack));
cnt =
0; index = 0; top = 0;
memset(dfn, 0, sizeof(dfn));
for(int
i = 1; i <= n; i++) //i从1还是0开始视题目而定
while(scanf("%d%d", &n,
&m) != EOF)
{
for(int i = 1; i
<= n; i++) v[i].clear();
for(int i = 0; i
< m; i++)
{
int a, b;scanf("%d%d", &a,
&b);
v[a].push_back(b);
}
solve();
memset(cd, 0,
sizeof(cd));
memset(rd, 0,
sizeof(rd));
for(int i = 1; i
<= n; i++)
for(int j = 0; j < v[i].size();
j++)
if
(belong[i] != belong[v[i][j]])
{
cd[belong[i]]++;
rd[belong[v[i][j]]]++;
}
int ans1 = 0, ans2 = 0;
for(int i = 0; i
< cnt; i++)
{
if (cd[i] == 0) ans1++;
if (rd[i] == 0) ans2++;
}
printf("%d\n", n
<= 1 || cnt <= 1? 0 : max(ans1,
ans2));
}
return
0;
有n个集合，m个关系，每个关系i，j，表示i集合是j集合的子集。
问你最少再添加几个关系，能够让所有的集合都相同。
解题报告：
其实就是再加多少条边，变成一个连通图。
先tarjan缩点后，图上就剩下一些点或者线（1->2 1->3 1->4算作3条线）
发现，只要首尾相连就是最优的方式。
所以，点或者线的数目就是图中max(出度为0的点，入度为0的点）。
就是答案。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define SIZE 20001
int n, m;
int belong[SIZE], num[SIZE], cnt;
int dfn[SIZE], low[SIZE], index, instack[SIZE], sta[SIZE],
top;
vector<int> v[SIZE];
int cd[SIZE], rd[SIZE];
void tarjan(int id)
{
}
void solve()
{
if (!dfn[i]) tarjan(i);
}
int main()
{
}
喜欢
0
赠金笔