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;
}



郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。