Codeforces Round #365 (Div. 2) B

http://codeforces.com/contest/703/problem/B

题意：

每个点都有一个值，每条边的权值为这两个点相乘。1~n成环。现在有k个城市，城市与其他所有点都相连，计算出所有边权值和。

思路：

每个城市要与其它所有城市都相连，所以我们可以先去计算城市的，先预处理一下，计算出所有点的值的和，那么每个城市乘以所有点的值的和减去它自身的值。

但是这样的话每两个城市之间就计算了两遍，要减去，具体看代码。

最后再考虑环上的点，如果还有边未计算，就加上去。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<string>
 6 #include<vector>
 7 #include<queue>
 8 #include<cmath>
 9 using namespace std;
10 typedef long long LL;
11 
12 const int maxn=1e5+5;
13 
14 int n,k;
15 int a[maxn];
16 int b[maxn];
17 int vis[maxn];
18 LL sum;
19 LL summ;
20 
21 int main()
22 {
23     //freopen("D:\input.txt","r",stdin);
24     while(~scanf("%d%d",&n,&k))
25     {
26         sum=0; summ=0;
27         for(int i=1;i<=n;i++)
28         {
29             scanf("%d",&a[i]);
30             sum+=a[i];    //所有点的和
31             vis[i]=0;
32         }
33         for(int i=1;i<=k;i++)
34         {
35             scanf("%d",&b[i]);
36             summ+=a[b[i]];  //城市的和
37             vis[b[i]]=1;
38         }
39 
40         LL ans=0;
41         for(int i=1;i<=k;i++)
42         {
43             ans+=a[b[i]]*(sum-a[b[i]]);
44         }
45         
46         //去重
47         LL temp=0;
48         for(int i=1;i<=k;i++)
49         {
50             temp+=a[b[i]]*(summ-a[b[i]]);
51         }
52         temp/=2;
53         ans-=temp;
54         
55         //计算环上还未计算的
56         for(int i=1;i<n;i++)
57         {
58             if(vis[i]==0 && vis[i+1]==0)
59                 ans+=a[i]*a[i+1];
60         }
61         if(vis[1]==0 && vis[n]==0)
62             ans+=a[1]*a[n];
63         printf("%lld
",ans);
64     }
65     return 0;
66 }