首页 > 代码库 > cogs1355. 读书 x
cogs1355. 读书 x
1355. 读书
★ 输入文件：reading.in 输出文件：reading.out 简单对比
时间限制：1 s 内存限制：128 MB
【题目描述】
放暑假了，CHH想趁假期提高一下自己的计算机水平，于是他从学校图书馆借了N本计算机科学方面的书，这N本书的编号依次为0～N-1。
读完第i本书，CHH需要花费time[i]分钟，但是有一些书的内容是相近的，如果第i本书与第j本书内容相近，那么如果CHH读完了第i本书，再读第j本书的时候只需要floor(time[j]/2)分钟的时间即可（其中floor()表示对括号中的式子进行下取整）；当然，如果CHH先读完了第j本书，那么再读第i本书的时候只需floor(time[i]/2)的时间。现在你的任务是告诉CHH，他最少可以用多少分钟读完这N本书。
【输入格式】
第一行有两个整数N（0<=N<=100）和M(0<=M<=N(N-1)/2)。N为书的总数，有M对书内容相近。
接下来有N行，分别表示time[0],time[1],...及time[N-1],(1<=time[i]<=10^5)。
再接下来有M行，每行有两个整数（i,j），表示第i本书与第j本书内容相近。
输入文件以N=0,M=0表示结束。
【输出格式】
对于每组测试数据，输出仅一行，即最少时间。
【样例输入】
2 16100 13 21230 11 23 12460 10 0
【样例输出】
11310
【提示】
对于第一组数据，如果CHH读的顺序为（0，1），则总的时间为6+10/2=11，如果读的顺序为（1，0），则总的读书时间为10+6/2=13.
思路:
题目中提及:
2本书之间可能内容相近，所以我们可以采用并查集，然后贪心选一个集合中用时最小的书，剩下的除2加入总时间即可。
故我们可以用kruskal来做这道题
坑点:
1)若出现m==0但是n!=0，此时不要退出程序！！！
2)要从0开始进行标号
上代码:
#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>#include <cmath> using namespace std;const int N = 110;const int M = 5050;int n,m,ans;int t[N],dad[N];bool vis[N];int getdad(int x){return dad[x] == x ? x : dad[x] = getdad(dad[x]);}void kruskal(){ while(true) { int flag=-1; int tmp[200]={0},cnt=0; for(int i=0;i<n;i++) { if(flag==-1 && !vis[i]) { vis[i]=true; flag=getdad(i); tmp[++cnt]=t[i]; } else if(flag!=-1 && !vis[i] && getdad(i)==flag) { vis[i]=true; tmp[++cnt]=t[i]; } } if(!cnt) { cout<<ans<<endl; break; } sort(tmp+1,tmp+1+cnt); ans+=tmp[1]; for(int i=2;i<=cnt;i++) ans+=floor(tmp[i]>>1); }}void chu(){ ans=0; memset(t,0,sizeof(t)); memset(vis,false,sizeof(vis)); memset(dad,0,sizeof(dad));}int main(){ freopen("reading.in","r",stdin); freopen("reading.out","w",stdout); while(cin>>n>>m) { if(n==0 && m==0) break; chu(); for(int i=0;i<n;i++) cin>>t[i],dad[i]=i; for(int i=0,u,v;i<m;i++) { cin>>u>>v; int f1=getdad(u),f2=getdad(v); if(f1!=f2) dad[f1]=f2; } kruskal(); } return 0;}
cogs1355. 读书 x