题目链接
题目翻译：
小镇上有n个地区，第i个地区属于帮派ai。最开始所有地区之间都没有道路连接。 你是这个城市的市长，并想建立n-1条道路连接所有地区（两个地区可以被直接连接，也可以通过其它地区间接连接）。 如果两个属于同一帮派的地区被直接连接，则会起冲突。 你不想让这种事情发生，所以你的任务是建立n-1条道路，使得所有的地区都是可以相互抵达的（可能通过其他地区抵达）并且任意两个直接连接的地区属于不同的帮派。或者回答无法建立满足条件的n-1条道路。 你需要回答t个独立的测试用例。
我的解题思路：
可以先整理出所有属于同一帮派的地区，再以下图的方式连接所有地区。 先拿出一个1，把所有2都连接到这个1上，再把所有3都连接到同一个2上，以此类推，最后把剩下的1都连接到同一个4上就可以了。这样所有属于相同帮派的地区就不会相连接了。 另一个就是怎么判断结果是否存在。显然，当所有地区都属于同一帮派的时候，结果不存在。
我的代码：
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdio>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std
;
vector
<int>v
,vv
[5010];
map
<int,int>mm
;
int main() {
int t
,n
,a
;
cin
>>t
;
while(t
--) {
cin
>>n
;
v
.clear();
mm
.clear();
int num
=1,maxlen
=0,maxnum
=0;
for(int i
=1; i
<=n
; i
++) {
cin
>>a
;
if(mm
[a
]==0) {
mm
[a
]=num
;
vv
[num
].clear();
num
++;
}
vv
[mm
[a
]].push_back(i
);
if(vv
[mm
[a
]].size()>maxlen
) {
maxlen
=vv
[mm
[a
]].size();
maxnum
=mm
[a
];
}
}
if(maxlen
==n
){
cout
<<"NO"<<endl
;
continue;
}
cout
<<"YES"<<endl
;
int start
= vv
[1][0];
for(int i
=2;i
<num
;i
++){
for(int j
=0;j
<vv
[i
].size();j
++){
cout
<<start
<<" "<<vv
[i
][j
]<<endl
;
}
start
=vv
[i
][0];
}
for(int i
=1;i
<vv
[1].size();i
++){
cout
<<start
<<" "<<vv
[1][i
]<<endl
;
}
}
return 0;
}
官方的解题思路：
看了答案，比我想的简单多了，随便找出一个任意帮派a的地区，将其他所有不属于帮派a的地区都连接到这个地区上，最后把帮派a剩余的地区连接到任意一个不属于帮派a的地区上。
代码：
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdio>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std
;
const int N
= 5050;
int a
[N
];
vector
<int>v
;
int main(){
int t
,n
,flag
,k
;
cin
>>t
;
while(t
--){
cin
>>n
;
v
.clear();
flag
=0;
for(int i
=1;i
<=n
;i
++){
cin
>>a
[i
];
if(a
[i
]!=a
[1]) flag
=1;
}
if(flag
==0){
cout
<<"NO"<<endl
;
continue;
}
cout
<<"YES"<<endl
;
for(int i
=2;i
<=n
;i
++){
if(a
[i
]==a
[1]) v
.push_back(i
);
else{
cout
<<1<<" "<<i
<<endl
;
k
=i
;
}
}
for(int i
=0;i
<v
.size();i
++){
cout
<<k
<<" "<<v
[i
]<<endl
;
}
}
return 0;
}
总结：
有思路之后还是应该再多想几分钟，换种思路可能花费的时间就会少很多很多。一开始理解错了，以为所有的地区应该连成一条直线，到最后了才反应过来…
