ZOJ 3708 Density of Power Network(水题)
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3708
题意:
题意挺简单的,就是数一下有多少种线路,并处以公交车的数量。题目的图很吓人,如果被这唬了的话就惨了,省赛的时候每道题都应该仔细看过,以免造成不必要的损失。
解法一:
队友用的方法是用一张二维图来表示,如果对应位置已经被标记过了,就不加入计数,如果没标记过,就标记,并计数值加一。
代码:
#include<iostream> #include<string> #include<iomanip> #include<cstring> using namespace std; int a[505],b[505]; int map[505][505]; int main() { int T,bus,m; cin>>T; while(T--) { cin>>bus>>m; memset(map,0,sizeof(map)); int sum=0; for(int i=1;i<=m;i++) { cin>>a[i]; } for(int i=1;i<=m;i++) { cin>>b[i]; } for(int i=1;i<=m;i++) { if(map[a[i]][b[i]]||map[b[i]][a[i]]) continue; else { map[a[i]][b[i]]=1; sum++; } } double ans; ans=sum*1.0/(bus*1.0); cout<<fixed<<setprecision(3)<<ans<<endl; } }
我的想法是可以取小的那个乘以1000(因为原始数据最多只到500,所以能够区分),再加上大的那个,用set排重就行了。
代码:
#include <iostream> #include <string> #include <iomanip> #include <set> #include <algorithm> using namespace std; int a[505],b[505]; int main() { int T,bus,m,minn,maxx; cin>>T; while(T--) { set <int> cnt; cin>>bus>>m; for(int i=1;i<=m;i++) { cin>>a[i]; } for(int i=1;i<=m;i++) { cin>>b[i]; } for(int i=1;i<=m;i++) { minn=min(a[i],b[i]); maxx=max(a[i],b[i]); cnt.insert(minn*1000+maxx); } double ans; ans=cnt.size()*1.0/bus; cout<<fixed<<setprecision(3)<<ans<<endl; } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。