计算机学院大学生程序设计竞赛（2015’12）Happy Value

计算机学院大学生程序设计竞赛（2015’12）Happy Value

Happy Value

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1337    Accepted Submission(s): 392

Problem Description

In an apartment, there are N residents. The Internet Service Provider (ISP) wants to connect these residents with N – 1 cables.  However, the friendships of the residents are different. There is a “Happy Value” indicating the degrees of a pair of residents. The higher “Happy Value” is, the friendlier a pair of residents is. So the ISP wants to choose a connecting plan to make the highest sum of “Happy Values”.

Input

There are multiple test cases. Please process to end of file. For each case, the first line contains only one integer N (2<=N<=100), indicating the number of the residents. Then N lines follow. Each line contains N integers. Each integer H ij(0<=H ij<=10000) in i th row and j th column indicates that i th resident have a “Happy Value” H ijwith j th resident. And H ij(i!=j) is equal to H ji. H ij(i=j) is always 0.

Output

For each case, please output the answer in one line.

Sample Input

2 0 1 1 0 3 0 1 5 1 0 3 5 3 0

Sample Output

1 8

总是望着曾经的空间发呆，那些说好不分开的朋友不在了，转身，陌路。 熟悉的，安静了， 安静的，离开了， 离开的，陌生了， 陌生的，消失了， 消失的，陌路了。

#include #include #define MaxInt 9999999#define N 110int map[N][N],low[N],visited[N],n;int prim(){ int i,j,pos=1,min,result=0; memset(visited,0,sizeof(visited)); visited[1]=1; for(i=2; i<=n; i++) low[i]=map[pos][i]; for(i=1; ilow[j]) { min=low[j]; pos=j; } result+=min; visited[pos]=1; for(j=1; j<=n; j++) if(visited[j]==0&&low[j]>map[pos][j]) low[j]=map[pos][j]; } return result;}int main(){ int i,v,j,ans; while(scanf("%d",&n)!=EOF) { memset(map,MaxInt,sizeof(map)); for(i=1; i<=n; i++) for(j=1; j<=n; j++) { scanf("%d",&v); map[i][j]=-v; } ans=-1*prim(); printf("%d\n",ans); } return 0;}

@执念  "@-但求“❤”安★ 下次我们做的一定会更好。。。。

为什么这次的题目是英文的。。。。QAQ...

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。