@Asuna
2017-03-29T13:20:40.000000Z
字数 5403
阅读 913
题解
题意：给定n个人和m对关系，每一对关系表示两个人互相认识，互相认识的人都可以坐在一桌上，问最少需要多少桌。
题解：裸的并查集，把认识的人都合并一下然后n每次合并减小1就行了。
参考代码：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int t,n,m,fa[1010],a,b,c;int find(int x){int r=x;while (fa[r]!=r)r=fa[r];return r;}void join(int x,int y){int fx=find(x),fy=find(y);if (fx!=fy){fa[fx]=fy;n--;}}int main(){cin>>t;while(t--){cin>>n>>m;for (int i=1; i<=n; i++)fa[i]=i;for (int i=1; i<=m; i++){cin>>a>>b;join(a,b);}cout<<n<<endl;}return 0;}
题意：有n个节点，有两个操作：
I x y：把x作为y的子节点连上，他们的距离为abs(x-y)%1000。
E x:查询x到根节点的距离。
题解：每次询问的时候在查找根节点的同时完成整条路径上每一个点的距离更新即可。
参考代码：
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;int t,n,a,b,fa[20010],ans,d[20010];char c;int find(int x){if (fa[x]==x) return x;else{int r=find(fa[x]);d[x]+=d[fa[x]];//cout<<d[x]<<endl;fa[x]=r;return r;}}int main(){cin>>t;while (t--){ans=0;cin>>n;for (int i=1; i<=n; i++){fa[i]=i;d[i]=0;}while(cin>>c){if (c=='O') break;if (c=='E'){cin>>a;find(a);//cout<<"!!!!"<<find(a)<<endl;cout<<d[a]<<endl;}if (c=='I'){cin>>a>>b;fa[a]=b;d[a]=abs(a-b)%1000;//cout<<a<<" "<<d[a]<<endl;}}}return 0;}
题意：每人一句话，指向某个人是好人或者坏人，好人只说真话坏人只说假话，问最后能不能确定好人和坏人。
题解：范围是100000因此以100000为界限，数组1～100000表示第i个人是好人，100000～200000表示第i个人是坏人，如果A说B是坏人，那么将A（好）和B（坏）合并，将A（坏）和B（好）合并，如果A说B是好人，那么将A（好）和B（好）合并，将A（坏）和B（坏）合并。全部合并完从头扫一次判断如果最后A（好）和A（坏）在同一个集合，就无解。（一脸meng bi）
参考代码：
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>using namespace std;int fa[200010],n,a,b;int find(int x){if (fa[x]==x) return x;else{int r=find(fa[x]);fa[x]=r;return r;}}void join(int x,int y){int fx=find(x),fy=find(y);if (fx!=fy)fa[fx]=fy;}int main(){cin>>n;for (int i=1; i<=200000; i++)fa[i]=i;for (int i=1; i<=n; i++){cin>>a>>b;if (b==1){join(i,a);join(i+100000,a+100000);}else{join(i,a+100000);join(i+100000,a);}}for (int i=1; i<=n; i++)if (find(i)==find(i+100000)){cout<<"One face meng bi"<<endl;return 0;}cout<<"Time to show my power"<<endl;return 0;}
题意：典型题的好处就是题意已经解释得非常清楚了。
题解：分别记录当前结点的祖先和到祖先的距离，规定距离为0时为同类，为1时表示被祖先吃，为2时表示吃祖先。初始时每个元素的祖先是自己，距离为0。
讨论两种情况。
1、如果d=1，表示读入的x和y是同类，这时分别找到x,y和祖先fx,fy，如果fx=fy，说明他们是同一祖先。这时判断x和y到祖先的距离是否相等，显然，不相等证明这是一句假话。如果fx!=fy，说明x和y不在同一集合中，此时将这两个集合合并。合并时可以通过一个简单的向量关系算出fx->fy的距离，即dis[fx]=dis[y]-dis[x].
2、如果d=2，表示x吃y，同样的找到它们的祖先，若fx=fy，则根据向量关系判断它们的距离是否矛盾，没有矛盾之后可以和1中类似的通过向量关系算出距离。
参考代码：
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;int fa[50010],dis[50010],ans,n,k,d,x,y;int find(int x){if (fa[x]==x) return x;else{int r=fa[x];fa[x]=find(fa[x]);dis[x]=(dis[r]+dis[x])%3;return fa[x];}}int main(){ios::sync_with_stdio(false);cin>>n>>k;for (int i=1; i<=n; i++){dis[i]=0;fa[i]=i;}for (int i=1; i<=k; i++){scanf("%d%d%d",&d,&x,&y);if ((x>n) || (y>n)){ans++;continue;}int fx=find(x),fy=find(y);if (d==1){if (fx==fy){if (dis[x]!=dis[y]) ans++;continue;}fa[fx]=fy;dis[fx]=(dis[y]-dis[x]+3)%3;}if (d==2){if (x==y){ans++;continue;}if (fx==fy){if ((2-dis[x]+dis[y])%3!=0) ans++;continue;}fa[fx]=fy;dis[fx]=(dis[y]-dis[x]+2)%3;}}cout<<ans<<endl;return 0;}
题意：给你N个点M条路的图，点的变化由0~N-1，求最小生成树。
题解：直接用Kruskal直接求出就可以了。
参考代码：
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>using namespace std;struct node{int x,y,p;}e[200010];int fa[200010],sum,n,m;bool cmp(node a,node b){return a.p<b.p;}int find(int x){if (x!=fa[x])fa[x]=find(fa[x]);return fa[x];}void kruskal(int m,int n){int fx,fy;for (int i=0; i<m; i++)fa[i]=i;sort(e,e+n,cmp);for (int i=0; i<n; i++){fx=find(e[i].x);fy=find(e[i].y);if (fx!=fy){sum-=e[i].p;fa[fx]=fy;}}}int main(){while(cin>>m>>n){if ((n==0) && (m==0)) break;sum=0;for (int i=0; i<n; i++){scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].p);sum+=e[i].p;}kruskal(m,n);cout<<sum<<endl;}return 0;}
题意：给出各个点的距离，问这可不可能是一棵树。
题解：每次取最小的边，加入已生成的树中，会发现这就是一个最小生成树问题。所以我们只需要根据这个图构造一棵最小生成树。最后在BFS一遍去跟题目给的矩阵比较就行了。如果相同就是YES，否则就输出NO。
参考代码：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int a[2005][2005],n,fa[2005],q[2005],flag[2005],dist[2005][2005],cc=0,h[2005],d[2005][2005],k;struct edge{int from,to,dist;}e[4000010];int getfa(int k){if (k==fa[k])return k;return fa[k]=getfa(fa[k]);}void qsort(int low,int high){int i=low,j=high,t=e[(low+high)/2].dist;while (i<j){while (e[i].dist<t) i++;while (e[j].dist>t) j--;if (i<=j){int k;k=e[i].from; e[i].from=e[j].from; e[j].from=k;k=e[i].to; e[i].to=e[j].to; e[j].to=k;k=e[i].dist; e[i].dist=e[j].dist; e[j].dist=k;i++; j--;}}if (low<j) qsort(low,j);if (i<high) qsort(i,high);}void bfs(int k){memset(q,0,sizeof(q));memset(flag,0,sizeof(flag));int i,j;i=1; j=1;q[j++]=k; flag[k]=1;while (j-i>=1){for (int s=1;s<=h[q[i]];s++)if (!flag[d[q[i]][s]]){q[j++]=d[q[i]][s]; flag[d[q[i]][s]]=1;if (!dist[k][d[q[i]][s]]){dist[k][d[q[i]][s]]=dist[k][q[i]]+a[q[i]][d[q[i]][s]];dist[d[q[i]][s]][k]=dist[k][d[q[i]][s]];if (dist[k][d[q[i]][s]]!=a[k][d[q[i]][s]]){cout <<"NO"<<endl;cc=1;return;}}}i++;}}int main(){cin>>n;for (int i=1; i<=n; i++)for (int j=1; j<=n; j++){k++;scanf("%d",&a[i][j]);e[k].from=i;e[k].to=j;e[k].dist=a[i][j];}for (int i=1; i<=n; i++)for (int j=1; j<=i; j++){if (i==j && a[i][j]!=0){cout <<"NO"<<endl;return 0;}if (i!=j && a[i][j]==0){cout <<"NO"<<endl;return 0;}if (a[i][j]!=a[j][i]){cout <<"NO"<<endl;return 0;}}for (int i=1; i<=n; i++)fa[i]=i;qsort(1,k);for (int i=1; i<=k; i++){if (getfa(e[i].from)!=getfa(e[i].to)){int f1=getfa(e[i].from),f2=getfa(e[i].to);fa[f1]=fa[f2];d[e[i].from][++h[e[i].from]]=e[i].to;d[e[i].to][++h[e[i].to]]=e[i].from;}}for (int i=1; i<=n; i++){bfs(i);if (cc) return 0;}cout <<"YES"<<endl;return 0;}