首页 > 其他 > 详细

[CSP-S模拟测试]:联合权值·改(暴力)

时间:2019-11-11 21:27:17      阅读:98      评论:0      收藏:0      [点我收藏+]

题目传送门(内部题143)


输入格式

  输入文件的第一行为三个整数$n,m,t$。其中$t$是数据类型。
  接下来$m$行,每行两个正整数$u,v$,表示图中的一条边。数据保证不存在重边或自环的情况。    
  输入数据的最后一行是$n$个正整数,表示$W_1,W_2,...,W_n$。


输出格式

  输出文件共包含两行两个整数。第一行,若$t\neq 2$,则你需要输出最大的联合权值(无则输出$-1$),否则输出$0$;第二行,若$t\neq 1$,则你需要输出联合权值的总和,否则输出$0$。


样例

样例输入:

4 4 3
1 2
1 3
2 3
2 4
100 1 100 1

样例输出:

100
400


数据范围与提示

  对于$10\%$的数据,满足$n\leqslant 100$。
  对于另$30\%$的数据,满足$t=1$。
  对于另$30\%$的数据,满足$t=1$。
  对于$100\%$的数据,满足$1\leqslant n,m\leqslant 30,000,1\leqslant t\leqslant 3,1\leqslant W_i\leqslant 100$。


题解

暴力$95$,然而我读错题了……

只要$w$不一样就行,然而我还以为是一道$SB$题(不过本来也是)。

发现求和很好求,考虑求最大值。

去**正解。

考虑剪枝。

可以把连向一个点的所有点按点权从大到小排序,枚举点的时候找到最先的一组$break$就好了。

时间复杂度:$\Theta(n^2)$。

期望得分:$10$分。

实际得分:$100$分。


代码时刻

#include<bits/stdc++.h>
using namespace std;
int n,m,t;
int w[30001];
bitset<30000> bit[30001];
vector<int> vec[30001];
int mx;
long long ans;
bool cmp(int a,int b){return w[a]>w[b];}
int main()
{
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		vec[u].push_back(v);
		vec[v].push_back(u);
		bit[u][v]=bit[v][u]=1;
	}
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	for(int i=1;i<=n;i++)sort(vec[i].begin(),vec[i].end(),cmp);
	for(int x=1;x<=n;x++)
		for(int i=0;i<vec[x].size();i++)
			for(int j=i+1;j<vec[x].size();j++)
			{
				if(bit[vec[x][i]][vec[x][j]])continue;
				mx=max(mx,w[vec[x][i]]*w[vec[x][j]]);
				break;
			}
	for(int x=1;x<=n;x++)
	{
		int l=0,r=0;
		for(int i=0;i<vec[x].size();i++)
		{
			ans-=1LL*w[x]*w[vec[x][i]]*(bit[x]&bit[vec[x][i]]).count();
			l+=w[vec[x][i]];r+=w[vec[x][i]]*w[vec[x][i]];
		}
		ans+=1LL*l*l-r;
	}
	printf("%d\n%lld\n",(t==2)?0:mx,(t==1)?0:ans);
	return 0;
}

rp++

[CSP-S模拟测试]:联合权值·改(暴力)

原文:https://www.cnblogs.com/wzc521/p/11838110.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!