题意:
总共有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; }