一支分散的飞船舰队，需要汇合到主舰，但是这种飞船在太空中飞行的耗油与质量没有关系，只与发动机打开的时间有关系，为了节省油量，指挥官通知，汇合途中，多台飞船可以串成串飞行，这样只需启动一台发动机，由于安全因素飞船只能走某些航线（某飞船到某飞船的航线）。指挥发现这样的移动方案可能有多种，但最短汇合时间相同，指挥官想考察你是否知道在总耗油最小的情况下，最短多久汇合完毕。
Input
T（T<10）组数据每组第一行有一个整数N（飞船个数<=300），之后第一行是其他飞船到主舰的时间，再有n行，每行n个数Aij表示Ai到Aj的时间。（均在int范围内）
Output
每组数据输出总耗油最小的情况下，总耗油量与最短汇合时间。
Sample Input
1
5
5 7 4 3 6
0 2 1 6 3
2 0 3 1 4
1 3 0 4 5
6 1 4 0 2
3 4 5 2 0
Sample Output
9 7
题解: 铭轩出的题,真是好题啊....比赛的时候,最小生成树建图建错了....最后才懂,最小生成树(Prim和kruskal都可以)+搜索(最小值最大化)....存图的时候必须是半张图..不然会WA...蒟蒻啊....
WA代码:
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
using namespace std; #define MAX 1010
#define INF 0x3f3f3f3f struct edge
{
int x,y,cost;
}; edge e[MAX*MAX];
int f[MAX];
int dis[MAX];
int v,n,ans;
int mapp[][],pan[]; bool cmp(edge a,edge b)
{
return a.cost<b.cost;
} void init(int n)
{
for(int i=;i<=n;i++)
f[i]=i;
} int find(int x)
{
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
} void Union(int x,int y)
{
x=find(x);
y=find(y);
f[y]=x;
} int same(int x,int y)
{
return find(x)==find(y);
} int kruskal(int n,int m)
{
sort(e,e+m,cmp);
init(n);
int ans=;
for(int i=;i<m;i++)
{
if(!same(e[i].x,e[i].y))
{
Union(e[i].x,e[i].y);
ans+=e[i].cost;
mapp[e[i].x][e[i].y]=e[i].cost;
mapp[e[i].y][e[i].x]=e[i].cost;
}
}
return ans;
} int maxx=;
void dfs(int x,int step) {
for (int i=; i<=n; i++) {
if (mapp[x][i] && !pan[i]) {
pan[i]=;
dfs(i,step+mapp[x][i]);
}
}
if (maxx<step) maxx=step;
} int main()
{
int t;
scanf("%d",&t);
while(t--){
memset(mapp,,sizeof(mapp));
memset(pan,,sizeof(pan));
memset(e,,sizeof(e));
int v=;
scanf("%d",&n);
int count;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
e[v].x=i;
e[v].y=j;
scanf("%d",&count);
e[v++].cost=count;
}
int p=kruskal(n,v); pan[]=;
dfs(,); printf("%d %d\n",p,maxx);
}
}
AC代码:
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
using namespace std; #define MAX 1010
#define INF 0x3f3f3f3f struct edge
{
int x,y,cost;
}; edge e[MAX*MAX];
int f[MAX];
int dis[MAX];
int v,n,ans;
int mapp[][],pan[]; bool cmp(edge a,edge b)
{
return a.cost<b.cost;
} void init(int n)
{
for(int i=;i<=n;i++)
f[i]=i;
} int find(int x)
{
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
} void Union(int x,int y)
{
x=find(x);
y=find(y);
f[y]=x;
} int same(int x,int y)
{
return find(x)==find(y);
} int kruskal(int n,int m)
{
sort(e,e+m,cmp);
init(n);
int ans=;
for(int i=;i<m;i++)
{
if(!same(e[i].x,e[i].y))
{
Union(e[i].x,e[i].y);
ans+=e[i].cost;
mapp[e[i].x][e[i].y]=e[i].cost;
mapp[e[i].y][e[i].x]=e[i].cost;
}
}
return ans;
} int maxx=;
void dfs(int x,int step) {
for (int i=; i<=n; i++) {
if (mapp[x][i] && !pan[i]) {
pan[i]=;
dfs(i,step+mapp[x][i]);
}
}
if (maxx<step) maxx=step;
} int main()
{
int t;
scanf("%d",&t);
while(t--){
memset(mapp,,sizeof(mapp));
memset(pan,,sizeof(pan));
memset(e,,sizeof(e));
int v=;
scanf("%d",&n);
int count;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
scanf("%d",&count);
if(i<j){
e[v].x=i;
e[v].y=j;
e[v++].cost=count;
}
}
int p=kruskal(n,v); pan[]=;
dfs(,); printf("%d %d\n",p,maxx);
}
}