aptx4869
#199. APTX4869
描述
提交
自定义测试
【题目描述】：
为了帮助柯南回到一米七四，阿笠博士夜以继日地研究APTX4869的解药。他得出了如下结果：
1.解药由n种原料构成；
2.对于两种不同的的原料a,b，它们之间有个影响值f(a,b)；
3.需要把所有原料分成两部分X,Y，每部分中至少有一种原料；
4.解药的效果由分别属于X,Y的原料之间，最小的影响值决定，即
效果=min{f(a,b)|a∈X,b∈Y)}
博士需要你帮忙求出：在所有的方案中，最大的效果值可以是多少？
【输入描述】：
多组数据(<=10)，处理到EOF。
每组数据输入第一行为一个正整数n。
接下去是一个n行n列的整数矩阵，同一行的数以空格隔开。矩阵第i行j列表示第i种和第j种材料的影响值f(i,j)。给出的矩阵是对称的，即f(i,j)=f(j,i)。当i=j时，f(i,i)没有意义，矩阵该处的值为-1。
【输出描述】：
每组数据输出一行，表示最大可能的效果值。
【样例输入】：
3
-1 100 300
100 -1 200
300 200 -1
【样例输出】：
200
【时间限制、数据范围及描述】：
时间：1s 空间：64M
2<=n<=800。当i!=j时，0<=f(i,j)<=1,000,000；当i=j时，f(i,j)=-1。
#include<stdio.h>
#include<algorithm>
#include<iOStream>
#include<string.h>
#include<queue>
using namespace std;
int bin[1000];
int shen[1000];
int ju[1000][1000];
typedef struct pp
{
int x;
int y;
int cost;
} ss;
ss aa[1000000];
bool cmp(pp n,pp m)
{
return n.cost<m.cost;
}
int main(void)
{
int i,j,k;
while(scanf("%d",&k)!=EOF)
{
for(i=0; i<=1000; i++)
{
shen[i]=1;
bin[i]=i;
}
for(i=1; i<=k; i++)
{
for(j=1; j<=k; j++)
{
scanf("%d",&ju[i][j]);
}
}
int cnt=0;
for(i=1; i<=k; i++)
{
for(j=i+1; j<=k; j++)
{
aa[cnt].cost=ju[i][j];
aa[cnt].x=i;
aa[cnt].y=j;
cnt++;
}
}
sort(aa,aa+cnt,cmp);
int coutt=0;
for(i=0; i<cnt; i++)
{
int xx;
int yy;
for(xx=aa[i].x;xx!=bin[xx];)
xx=bin[xx];
for(yy=aa[i].y;yy!=bin[yy];)
yy=bin[yy];
if(xx!=yy)
{
coutt=aa[i].cost;
if(shen[xx]>shen[yy])
{
shen[xx]+=shen[yy];
bin[yy]=xx;
}
else
{
shen[yy]+=shen[xx];
bin[xx]=yy;
}
}
}printf("%d\n",coutt);
}return 0;
}
文章创建于: 2019-09-12 21:47:20