http://202.120.80.191/problem.php?problemid=2614
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int maxn=110;
int g[maxn][maxn],pre[maxn];
int maxbetween[maxn][maxn];
int x[maxn],y[maxn];
int n;
int ans;
void init()
{
for(int i=0;i<n;i++)
{
g[i][i]=0;
for(int j=i+1;j<n;j++)
g[i][j]=g[j][i]=abs(x[i]-x[j])+abs(y[i]-y[j]);
}
}
int prim(int u)
{
int ans=0;
int k,smin;
int dist[maxn];
bool visit[maxn];
memset(maxbetween,0,sizeof(maxbetween));
for(int i=0;i<n;i++)
{
dist[i]=g[u][i];
visit[i]=0;
pre[i]=u;
}
visit[u]=1;
pre[u]=-1;
for(int i=1;i<n;i++)
{
k=-1;
smin=INT_MAX;
for(int j=0;j<n;j++)
if(!visit[j] && dist[j]<smin)
{
k=j;
smin=dist[j];
}
//if(k==-1) continue;
for(int j=0;j<n;j++)
if(visit[j])
maxbetween[j][k]=maxbetween[k][j]=max(maxbetween[j][pre[k]],smin);
ans+=smin;
visit[k]=1;
for(int j=0;j<n;j++)
if(!visit[j] && g[k][j]<dist[j])
{
dist[j]=g[k][j];
pre[j]=k;
}
}
return ans;
}
int unique()
{
int res=INT_MAX;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(i!=j && i!=pre[j] && j!=pre[i] )
res=min(res,ans-maxbetween[i][j]+g[i][j]);
return res;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d%d",&x[i],&y[i]);
init();
ans=prim(0);
printf("%d\n%s\n",ans,unique()==ans?"Yes":"No");
}
}