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

题目传送门（内部题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++

巴特西