《算法競(jìng)賽·快沖300題》將于2024年出版，是《算法競(jìng)賽》的輔助練習(xí)冊(cè)。
所有題目放在自建的OJ New Online Judge。
用C/C++、Java、Python三種語(yǔ)言給出代碼，以中低檔題為主，適合入門、進(jìn)階。
“ 糖果配對(duì)” ，鏈接： http://oj.ecustacm.cn/problem.php?id=1735
題目描述
【題目描述】 現(xiàn)在有N個(gè)小朋友，有M個(gè)不同的糖果。每個(gè)小朋友有自己最喜歡的糖果和第二喜歡的糖果。
?? 給定一些糖果，小朋友們會(huì)排隊(duì)來(lái)領(lǐng)糖果，對(duì)于每個(gè)小朋友而言，如果其最喜歡的糖果還在，將會(huì)選擇最喜歡的糖果，否則選擇第二喜歡的糖果。
?? 如果二者都不在，那么這個(gè)小朋友將會(huì)哇哇大哭。
?? 你可以任意排列對(duì)小朋友排隊(duì)的順序，但是要保證哭的小朋友數(shù)量最小。
?? 請(qǐng)求出最小的哭泣小朋友的數(shù)量。
【輸入格式】 輸入格式
?? 輸入第一行包含N和M。(N,M≤100000)
?? 接下來(lái)有N行，每i行包含兩個(gè)數(shù)字fi和si表示第i個(gè)小朋友最喜歡和第二喜歡的糖果編號(hào)。
【輸出格式】 輸出一個(gè)數(shù)字表示答案。
【輸入樣例】
8 10
2 1
3 4
2 3
6 5
7 8
6 7
7 5
5 8
【輸出樣例】
1
題解
?? 每個(gè)孩子有最喜歡的糖果和次喜歡的糖果，從二者中選擇一個(gè)，相當(dāng)于一個(gè)孩子連接了兩個(gè)糖果。把孩子和糖果建模為一個(gè)圖，孩子是圖上的邊，糖果是圖上的點(diǎn)。要求每條邊和每個(gè)點(diǎn)進(jìn)行配對(duì)，問(wèn)最多有多少個(gè)點(diǎn)和邊能夠匹配？
?? 把樣例畫(huà)成下面的圖，圖中的邊是孩子，點(diǎn)是孩子喜歡的糖果。例如邊{1-2}是第1個(gè)孩子喜歡的糖果1、2。根據(jù)樣例的數(shù)據(jù)畫(huà)出2個(gè)連通子圖，一個(gè)子圖是{1,2,3,4}，它是一棵樹(shù)；一個(gè)子圖是{5,6,7,8}，它是一個(gè)有環(huán)圖。
?? 容易分析得出：如果連通子圖是一棵樹(shù)，則匹配的數(shù)量就等于邊數(shù)，或者等于點(diǎn)的數(shù)量減一；如果連通子圖是一個(gè)有環(huán)圖，匹配的數(shù)量就等于點(diǎn)數(shù)。例如上圖中，左邊子圖是有3條邊的樹(shù)，能滿足3個(gè)小朋友；右邊子圖是有4個(gè)點(diǎn)的有環(huán)圖，能滿足4個(gè)小朋友。
?? 本題經(jīng)過(guò)轉(zhuǎn)換后是這樣一個(gè)圖的連通性問(wèn)題：（1）構(gòu)造圖；（2）查詢其中有多少連通子圖；（3）對(duì)每個(gè)子圖，區(qū)分它是樹(shù)還是有環(huán)圖，分別統(tǒng)計(jì)邊和點(diǎn)的數(shù)量。
?? 圖的連通性，編碼可以用BFS、DFS、并查集。下面用編碼比較簡(jiǎn)單的并查集求解。
?? 首先讀取點(diǎn)和邊，用并查集處理，屬于同一個(gè)子圖的點(diǎn)，它們的集都相同，同時(shí)用ring標(biāo)注這個(gè)集是否是有環(huán)圖。
?? 如何用并查集處理有環(huán)圖？讀2個(gè)點(diǎn)u、v構(gòu)成的邊u-v時(shí)，如果發(fā)現(xiàn)u、v已經(jīng)在以前讀取和處理過(guò)，且屬于一個(gè)集，說(shuō)明邊u-v把原來(lái)的子圖變成了一個(gè)有環(huán)圖。
?? 讀取和處理完所有的點(diǎn)和邊后，上面圖示的的兩個(gè)子圖變成了下面的兩個(gè)并查集。并查集2中包含點(diǎn){1, 2, 3, 4}，并查集6中包含點(diǎn){5, 6, 7, 8}。
?? 請(qǐng)注意兩個(gè)關(guān)鍵：
?? （1）并查集必須用路徑壓縮，這樣才能使得一個(gè)集中的每個(gè)點(diǎn)所屬的集相同，例如{1, 2, 3, 4}都屬于并查集2。
?? （2）需要標(biāo)記每個(gè)并查集是樹(shù)還是有環(huán)圖。下面的代碼用參數(shù)ring來(lái)標(biāo)記一個(gè)點(diǎn)是否在有環(huán)圖上。只要這個(gè)并查集中有一個(gè)點(diǎn)的ring標(biāo)記為true，這個(gè)并查集就是一個(gè)有環(huán)圖。
?? 最后就是搜索有多少并查集，并統(tǒng)計(jì)每個(gè)并查集內(nèi)部有多少個(gè)糖果匹配。只需用O(nlogn)的計(jì)算量即可完成這2個(gè)任務(wù)：
?? （1）對(duì)所有并查集按集的大小排序，例如{1, 2, 3, 4}、{5, 6, 7, 8}這個(gè)兩個(gè)并查集的點(diǎn)對(duì)應(yīng)的集是{2, 2, 2, 2}、{6, 6, 6, 6}，按集的大小排序后，同一個(gè)集的點(diǎn)都排在一起。排序的計(jì)算量為O(nlogn)。
?? （2）從小到大遍歷所有的集，如果集的大小一樣，它們就屬于一個(gè)集。統(tǒng)計(jì)這個(gè)集內(nèi)部的糖果匹配數(shù)量。計(jì)算量為O(n)。
【重點(diǎn)】 圖的連通性 。
C++代碼
??文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-657736.html
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
struct child {int s; bool ring;} c[N]; //s: 并查集； ring：這個(gè)點(diǎn)是否在一個(gè)有環(huán)圖上
bool cmp(struct child a, struct child b){ return a.s < b.s;} //按s排序
int find_set(int x){ //并查集：查詢
if(c[x].s!=x) c[x].s=find_set(c[x].s); //路徑壓縮
return c[x].s;
}
int main(){
int n,m; cin>>n>>m;
for(int i=1;i<=m;i++) c[i].s = i,c[i], c[i].ring = false; //并查集初始化
for(int i=1;i<=n;i++) {
int u,v; cin>>u>>v; //讀取一條邊上的兩個(gè)點(diǎn)
u = find_set(u); //查詢它們的集
v = find_set(v);
if(u==v){ //已經(jīng)是同一個(gè)集，說(shuō)明這個(gè)集是一個(gè)有環(huán)圖
c[u].ring = true; //標(biāo)注這個(gè)集是一個(gè)有環(huán)圖
continue; //已經(jīng)在一個(gè)集中了，不用合并
}
c[v].s = c[u].s; //u、v還不在一個(gè)集中，進(jìn)行并查集合并
}
for(int i=1;i<=m;i++)
find_set(i); //利用查詢進(jìn)行路徑壓縮，使同一個(gè)集的點(diǎn)的所屬的集相同
sort(c+1,c+m+1,cmp); //對(duì)集排序，讓同一個(gè)集的點(diǎn)排在一起
int tot = 0; //統(tǒng)計(jì)能滿足多少小朋友
for(int i=2;i<=m;i++) { //遍歷有多少個(gè)集
bool Ring = false; //這個(gè)集是否為有環(huán)圖，初始化為非環(huán)圖
int point = 1; //統(tǒng)計(jì)這個(gè)集表示的連通子圖內(nèi)有多少個(gè)點(diǎn)
while(c[i].s == c[i-1].s) { //如果兩點(diǎn)的集s相同，說(shuō)明它們屬于同一個(gè)子圖
if(c[i-1].ring || c[i].ring ) Ring = true; //這個(gè)集是一個(gè)有環(huán)圖
point++; //統(tǒng)計(jì)這個(gè)集合的點(diǎn)的數(shù)量
i++; //遍歷這個(gè)集
}
if(Ring==false) point--; //不是有環(huán)圖，是一棵樹(shù)
tot += point;
}
cout<<n-tot; //不能滿足的小朋友人數(shù)
return 0;
}
Java代碼
import java.util.*;
public class Main {
static class Child {
int s;
boolean ring;
public Child(int s, boolean ring) {
this.s = s;
this.ring = ring;
}
}
static Child[] c;
static int n, m;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
int N = 100010;
c = new Child[N + 1];
for (int i = 1; i <= N; i++) c[i] = new Child(i, false);
for (int i = 1; i <= n; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
u = findSet(u);
v = findSet(v);
if (u == v) {
c[u].ring = true;
continue;
}
c[v].s = c[u].s;
}
for (int i = 1; i <= m; i++) findSet(i);
Arrays.sort(c, 1, m + 1, new Comparator<Child>() {
public int compare(Child a, Child b) { return a.s - b.s; }
});
int tot = 0;
for (int i = 2; i <= m; i++) {
boolean ring = false;
int point = 1;
while (c[i].s == c[i - 1].s) {
if (c[i - 1].ring || c[i].ring) ring = true;
point++;
i++;
}
if (!ring) point--;
tot += point;
}
System.out.println(n - tot);
}
static int findSet(int x) {
if (c[x].s != x) c[x].s = findSet(c[x].s);
return c[x].s;
}
}
Python代碼
??文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-657736.html
import sys
sys.setrecursionlimit(1000000)
import functools
N = 100010
class Child:
def __init__(self, s, ring):
self.s = s
self.ring = ring
def cmp(a, b): return a.s - b.s
def find_set(x):
if c[x].s != x: c[x].s = find_set(c[x].s)
return c[x].s
c = []
n, m = map(int, input().split())
for i in range(N): c.append(Child(i, False))
for i in range(1,n+1):
u, v = map(int, input().split())
u = find_set(u)
v = find_set(v)
if u == v:
c[u].ring = True
continue
c[v].s = c[u].s
for i in range(1, m + 1): find_set(i)
c[1:] = sorted(c[1:], key=functools.cmp_to_key(cmp))
tot = 0
i = 2
while i <= m:
Ring = False
point = 1
while c[i].s == c[i - 1].s:
if c[i - 1].ring or c[i].ring: Ring = True
point += 1
i += 1
if not Ring: point -= 1
tot += point
i += 1
print(n - tot)
到了這里，關(guān)于《算法競(jìng)賽·快沖300題》每日一題：“糖果配對(duì)”的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
