#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <climits> using namespace std; const int MAX_N=110; const long long INF=LONG_LONG_MAX/2; int T,n,m,cases=0; long long data[MAX_N],dp[MAX_N][MAX_N]; void solve() { for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { dp[i][j]=INF; } } memset(dp[0],0,sizeof(dp[0])); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int k=1;k<=i;k++){ dp[i][j]=min(dp[k-1][j-1]+data[i]-data[k],dp[i][j]); } } } printf("Case #%d: %lld ",++cases,dp[n][m]); } int main() { //freopen("Ain.txt","r",stdin); scanf("%d",&T); data[0]=0; while(T--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%lld",&data[i]); } sort(data+1,data+n+1); solve(); } return 0; }
我们可以想一下，繁荣度是怎么来的？假设一个点的度是2，相当于以这个点为根，有两棵子树，那繁荣度就是这两棵子树上各取一个点两两组合，最后的结果就是两棵子树上的点的乘积。所以不难推出，若度大于2，那繁荣度就是所有子树上的点树两两相乘的和，例如上图的C点，度为3，且3个度包含的点的个数分别为1，1，3，繁荣度 = 1*1 + 1*3 + 1*3 = 7。
然而，这样的计算方式复杂度有点高，若度为n，光计算繁荣度就要O（n*n），更何况这只是一个点的繁荣度。所以，我们还可以简化一下计算方式：
计算出每一棵子树的点的个数，用每个子树的点的个数乘以除了这棵子树以及根节点以外剩余的点，，每棵子树都这样计算，并将结果相加，求出的和除以2，就是结果。
因为这样的计算方式和之前相比，相当于两两之间都乘了两次，子树1*所有子树的和（除自己） = 子树1*子树2* + 子树1*子树3 + ..... + 子树1*子树n， 子树2*所有子树的和（除自己） = 子树2*子树1 + 子树2*子树3 + ... + 子树2*子树n；这之中，子树1*子树2 ，又子树2*1子树，计算了两次，所以最终结果要除以2。
我们可以将整个图看成一棵以节点1为根的树，这样将会简化很多。除此之外，还可以使用链式前向星，记录下某个点与哪些点直接相连。这样，就可以节省寻找子树的时间
#include<iostream> #include<cstring> #include<cstdio> #include<string> #include<cmath> #include<algorithm> #include<stack> #include<climits> #include<queue> #define eps 1e-7 #define ll long long #define inf 0x3f3f3f3f #define pi 3.141592653589793238462643383279 using namespace std; const int maxn = 20007; int head[maxn],num,n; ll ans,sum,size[maxn]; struct node{ int to,next; }edge[maxn<<1]; void add(int u,int v) //使用链式前向星计算每个点于那些点直接相连 { edge[num].to = v; edge[num].next = head[u]; head[u] = num++; } void DFS(int u,int fa) //将整个图看成一棵树，u为当前节点，fa为父亲节点 { ll res = 0; size[u] = 1; //size[u]表示以u为根的树有多少个节点 for(int i=head[u]; i!=-1; i=edge[i].next) //遍历所有子树 { int to = edge[i].to; if(to == fa) continue; //不计算父亲节点 DFS(to,u); size[u] += size[to]; //以u为根的树的节点总数等于他所有子树的节点树之和 res += (n - size[to] - 1)*size[to]; //计算子树与其他剩余点的乘积 } res += ( n - size[u] )*(size[u]-1); //除所有子树外，u的根节点连成的树也是以u为根的一课子树 ans = max(ans,res/2); return; } int main() { int t,cnt = 1; cin>>t; while(t--) { ans = -1; num = 0; memset(head,-1,sizeof(head)); memset(size,0,sizeof(size)); scanf("%d",&n); int start,end; for(int i=0; i<n-1; ++i) { scanf("%d%d",&start,&end); add(start,end); //start于end直接相连 add(end,start);//无向图，反过来也相连 } DFS(1,-1); printf("Case #%d: %lld ",cnt++,ans); } return 0; }
完全的最小生成树的题目
#include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <cmath> #define MAXN 205 using namespace std; struct node { int u,v,d; }edge[MAXN*MAXN]; int father[MAXN]; int getfather(int x) { if (father[x]==x) return x; return father[x]=getfather(father[x]); } bool cmp(node a,node b) { return a.d<b.d; } int main() { int C,cases,N,K,M,i,u,v,f,ans; scanf("%d",&C); for (cases=1;cases<=C;cases++) { scanf("%d%d%d",&N,&M,&K); for (i=1;i<=N;i++) father[i]=i; scanf("%d",&f); for (i=2;i<=K;i++) scanf("%d",&u),father[u]=f; for (i=1;i<=M;i++) scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].d); sort(edge+1,edge+1+M,cmp); ans=0; for (i=1;i<=M;i++) { u=edge[i].u,v=edge[i].v; if (getfather(u)==getfather(v)) continue; ans+=edge[i].d; father[father[u]]=father[v]; } printf("Case #%d: %d ",cases,ans); } return 0; }