|
PICTURE:/home/ldu/.config/tencent-qq//AppData/file//sendpix0.jpg
来自oi-wiki
在上面的描述中，V是代表的点权，而E代表的是边权
独立集以及最大独立集均是点的集合
从字面意思来说，一张图的最大独立集就是独立集中大小最大的
如果说两个点之间是独立的那么说这两个点之间就没有边相连 匹配PICTURE:/home/ldu/.config/tencent-qq//AppData/file//sendpix1.jpg
上面所提到的独立集是点的集合，而匹配则是边的集合
在这个集合中，任一两条边之间是不含有公共的端点的
从字面意思来说，最大匹配也就是所包含的最大数量的边的数量，且任意两个边和边之间没有公共点
对于下面的图来说：
PICTURE:/home/ldu/.config/tencent-qq//AppData/file//sendpix2.jpg
对于这种图，有4个点3条边
最大独立集就是{2,3,4}
最大匹配就是{1-2} {1-3} {1-4} 中的任意一个其中1-2表示的意思为点1和点2之间的边 概念之间的关系及性质最大独立集 = n - 最大匹配 最大匹配 = 最小点覆盖 最大独立集 = n - 最小点覆盖 最大团 = 补图的最大独立集 最大独立集 = 补图的最大团
补图：如果n个点两两之间没有边，那么将这两个点连在一起，如果之前两点之间有边，那么就将这两个点之间的边去掉-》得到补图
整理到这里，我们可以发现在上面的图中，要是想知道二分图的最大独立集
可以先做出图的补图，得到补图之后可以从任意两点之间不相邻转换为两点之间相邻
PICTURE:/home/ldu/.config/tencent-qq//AppData/file//sendpix3.jpg
所以说很容易就能够看出这个图的最大独立集大小就是3 -> {2,3,4} 二分图的最大独立集 -> 一个最大的点的集合，该集合内的任意两点没有边相连。
二分图最大团的定义 -> 一个最大的点的集合，该集合内的任意两点都有边相连。
所以说上面的4.5.是相反的关系 例题2021年度训练联盟热身训练赛第一场 B Code Names 题目描述 You are given W, a set of N words that are anagrams of each other. There are no duplicate letters in any word. A set of words
S
⊆
W
S⊆W
S⊆W is called “swap-free” if there is no way to turn a word
x
∈
S
x∈S
x∈S into another word
y
∈
S
y∈S
y∈S by swapping only a single pair of (not necessarily adjacent) letters in x. Find the size of the largest swap-free set S chosen from the given set W.
输入描述: The first line of input contains an integer N (
1
≤
N
≤
500
1≤N≤500
1≤N≤500). Following that are N lines each with a single word. Every word contains only lowercase English letters and no duplicate letters. All N words are unique, have at least one letter, and every word is an anagram of every other word.
输出描述: Output the size of the largest swap-free set.
示例1
输入 6
abc
acb
cab
cba
bac
bca 输出
3 示例2
输入 11
alerts
alters
artels
estral
laster
ratels
salter
slater
staler
stelar
talers 输出
8 示例3
输入 6
ates
east
eats
etas
sate
teas 输出 4 要是求最大匹配 / 最小点覆盖问题，可以选择比较简单的匈牙利算法，代码篇幅比较短还比较容易实现
具体的博客内容推荐知乎 具体的思路是我们可以将之间能够swap free的建立关系（连一条边无向边）
然后跑匈牙利算法
然后在遍历n个点的时候，将符合条件的点进行统计-> cnt，然后 temp = cnt / 2 -> 会有一半的重复
最后answer = n - temp; judge函数用来判断两个字符串之间是不是能够建立联系，如果是能够通过交换两个字母得到，就在两个字符串之间建立一条边（实际在操作的过程中只是需要对字符串的下表进行建边就好，不会对答案产生影响） 在判断节点是否可行的时候注意将之前加的标注数组vis进行清空，否则会对答案产生影响 a数组是用来存储边的，vis数组用来标记节点是否已经被访问过，fa数组用来存储一个节点已经配对的节点的编号 对某一个点进行判断的时候，可以将所需要判断的点传参进入dfs函数，然后遍历和这个点相连的所有点节点，当与x节点相连的点没有被访问过的时候，我们就可以将这个点标记为访问过，并递归处理这个点，处理的条件是这个点没有与之建立匹配关系的节点，或者是这个点可以进行匹配，用上面博客里的一句话就是：//如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配。其中，左侧可以理解为二分图的另一部分，当然是和这个点不在同一块的部分 然后就可以输出n - cnt / 2即可
int a[507][507];
int fa[507];
int n;
string s[507];
bool vis[507];
bool judge(string a,string b){if(a.size() != b.size()) return false;
int len = a.size();
int cnt = 0;
int pos1,pos2;
for(int i=1;i<=len;i ){if(a[i-1] != b[i-1]){cnt ;
if(cnt > 2) return 0;
if(cnt == 1) pos1 = i-1;
else if(cnt == 2) pos2 = i-1;
}
}
if(a[pos1] != b[pos2]) return false;
if(a[pos2] != b[pos1]) return false;
return true;
}
bool dfs(int x){for(int i=1;i<=n;i ){if(i == x) continue;
if(a[x][i] && !vis[i]){vis[i] = 1;
if(!fa[i] || dfs(fa[i])){fa[i] = x;
return true;
}
}
}
return false;
}
int main()
{n = read;
memset(fa,0,sizeof fa);
memset(a,0,sizeof a);
for(int i=1;i<=n;i ) cin >> s[i];
for(int i=1;i<=n;i ){for(int j=i 1;j<=n;j ){if(judge(s[i],s[j])){a[i][j] = 1;
a[j][i] = 1;
}
}
}
int ans = 0;
for(int i=1;i<=n;i ){memset(vis,0,sizeof vis);
if(dfs(i)) ans ;
}
cout<<(n - (ans >> 1)) <<endl;
return 0;
}来源：https://www./content-4-884701.html
|
