题意:
总共有n个零食编号为1....n,有k个人,每个人的需求是x,y编号的零食,如果该编号有就吃,否则如果x和y都没有这个客人就会伤心,最后问如何排列客人吃的顺序,使得伤心的客人最少。
思路:
想不出来,太清奇了,题解是并查集的,把物品看作点,每个人看作两个物品间的边,对于一个有x元素的集合,存在且必定存在一种方式使得里面x-1个人都能满足,因为每次都能断掉一个边,由于第一次断的那条边会消去两个,别的方式都会消去一个。所有就是x-1,所以最后统计下每个集合的开心的人的数量就行了。
ac代码:
//My template
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<set>
#include<math.h>
#include<vector>
#include<queue>
#include<stack>
#include<iostream>
#include<sstream>
#define x first
#define y second
#define lson u<<1
#define rson u<<1|1
#define pb push_back
#define pu pushup
#define mk make_pair
using namespace std;
#define ll long long
#define debug puts("----");
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int p[100010];
int sz[100010];
int find(int x)
{
if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
p[i]=i,sz[i]=1;
for(int i=0;i<k;i++)
{
int a,b;
cin>>a>>b;
a=find(a),b=find(b);
if(a!=b)
p[a]=b,sz[b]+=sz[a];
}
for(int i=1;i<=n;i++)
if(find(i)==i)
{
//cout<<i<<endl;
k-=(sz[find(i)]-1);
}
cout<<k<<endl;
return 0;
}
京公网安备 11010502036488号