【Problem A-Zero or One】
【Description】Everyone probably knows the game Zero or One (in some regions in Brazil also known as Two or One), used to determine a winner among three or more players. For those unfamiliar, the game works as follows. Each player chooses a value between zero or one; prompted by a command (usually one of the contestants announces \Zero or... One!"), all participants show the value chosen using a hand: if the value chosen is one, the contestant shows a hand with an extended index finger; if the value chosen is zero, the contestant shows a hand with all fingers closed. The winner is the one who has chosen a value different from all others. If there is no player with a value different from all others (e.g. all players choose zero, or some players choose zero and some players choose one), there is no winner. Alice, Bob and Clara are great friends and play Zerinho all the time: to determine who will buy popcorn during the movie session, who will enter the swimming pool first, etc.. They play so much that they decided make a plugin to play Zerinho on Facebook. But since the don’t know how to program computers, they divided the tasks among friends who do know, including you. Given the three values chosen by Alice, Bob and Clara, each value zero or one, write a program that determines if there is a winner, and in that case determines who is the winner.
【Input】
The input contains a single line, with three integers A, B and C, indicating respectively the values chosen by Alice, Beto and Clara.
【Output】
Your program must output a single line, containing a single character. If Alice is the winner the character must be ‘A’, if Beto is the winner the character must be ‘B’, if Clara is the winner the character must be ‘C’, and if there is no winner the character must be ‘*’ (asterisc).
【題目大意】
三個人每個人為0或1摄杂，單獨的那一個勝利，輸出ABC循榆。如果沒有單獨的輸出’*’析恢。
【分析】
沒得分析
int main(){
int he=0,a,b,c;
scanf("%d%d%d",&a,&b,&c);
he=a+b+c;
if(he==1) {
if(a==1)printf("A");
if(b==1)printf("B");
if(c==1)printf("C");
}
else if(he==2) {
if(a==0)printf("A");
if(b==0)printf("B");
if(c==0)printf("C");
}
else printf("*");
}
=================================================================
【Problem C-Boss】
【Description】Everyone knows Iks, the last trend in social network, which made so much success that competitors like Facebook and Google+ are struggling to keep their own social networks in business. As several ".com" companies, Iks started in a small garage, but today employs hundreds of thousands. Iks has also a non-standard management system. For example, there are no committees or boards,
which means less time spent on internal meeting. However, as usual in other companies, there is a chain (or rather several chains) of command, as a person may manage other employees, and may be managed by other employees. A person P1 may manage another person P2 directly (when P1 is the immediate superior of P1) or indirectly (when P1 manages directly a person P3 who manages P2 directly or indirectly). A person does not manage himself/herself, either directly or indirectly. One folklore that developed in Wall Street is that Iks is so successful because in its chain of command a manager is always younger than the managed employee. As we can see in figure above, that is not true. But this folklore prompted Iks to develop a tool to study its own management system, and to understand whether age plays a role in its success. You have been hired to work on that tool. Given the description of the chain of command at Iks and the ages of its employees, write a program that answers a series of instructions. Instructions are of two types: management change and query. An instruction of management change swaps the positions of two employees A and B.
【Input】
Each test case is described using several lines. The first line of a test case contains three integers N, M and I, representing respectively the number of employees, the number of direct manage relations and the number of instructions. Employees are identified by numbers from 1 to N. The second line contains N integers Ki, where Ki indicates the age of the employee number i. Each of the following M lines contains two integers X and Y , indicating that X manages Y directly. Then it follows I lines, each describing an instruction. An instruction of type management change is described by a line containing the identifier T followed by two integers A and B, indicating the two employers that must swap places in the chain of command. An instruction of type query is described by a line containing the identifier P followed by one integer E, representing the number of an employer. The last instruction is of type query.
【Output】
For each instruction of type query your program must print a single line containing a single integer, the age of the employee who is the youngest person that manages the employer named in the query (directly or indirectly), if that person exists. If the employee does not have a manager, print an ‘*’ (asterisc).
【題目大意】
職場工作中有上下級的命令關(guān)系，稱之為命令鏈⊙硪現(xiàn)在給N名員工映挂，M條命令關(guān)系。員工的年齡在其后給出盗尸，緊接著M行x y表示x員工是y員工直接上級袖肥，在緊接著I行，每次表示修改或查詢振劳。修改則將兩名員工的管理關(guān)系對換，查詢則查詢某個員工的所有上級中最年輕的幾歲油狂。如果沒有輸出*历恐。
【分析】
Waiting for complement;
using namespace std;
typedef long long LL;
define maxn 510
define maxm 60100
struct node{
int y,next;
}a[maxm];int first[maxn],len;
int id[maxn],w[maxn],d[maxn];
void ins(int x,int y){
len++;a[len].y=y;
a[len].next=first[x];first[x]=len;
}
int ans;bool bo[maxn];
int mymin(int x,int y){return (x
void dfs(int x,int rt){
if (bo[x]) return;
bo[x]=true;
if (x!=rt) {
if (ans==-1) ans=d[id[x]];
else ans=mymin(ans,d[id[x]]);
}
for (int k=first[x];k!=-1;k=a[k].next) {
int y=a[k].y;
dfs(y,rt);
}
}
int main(){
int n,m,q,i,x,y;char c;
scanf("%d%d%d",&n,&m,&q);
len=0;memset(first,-1,sizeof(first));
for (i=1;i<=n;i++){
scanf("%d",&d[i]);
id[i]=i;w[i]=i;
//id[i]表示第i個位置是哪號人
//w[i]表示第i號人在第幾個位置
}
//建圖是建的位置
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
ins(y,x);
}
while (q--){
scanf("%c",&c);
while (c!='P' && c!='T') scanf("%c",&c);
if (c=='P') {
scanf("%d",&x);
memset(bo,false,sizeof(bo));
ans=-1;dfs(w[x],w[x]);
if (ans==-1) printf("*\n");
else printf("%d\n",ans);
}else if (c=='T') {
scanf("%d%d",&x,&y);
int tt=w[x];w[x]=w[y];w[y]=tt;
id[w[x]]=x;id[w[y]]=y;
}
}
return 0;
}
=================================================================
【Problem D-Folding Machine】
【Description】 One of the main tools of a Turing machine, which allows its computing power to be bigger than other simpler models, is an infinite tape, divided in cells, where information is stored. A Folding machine is a machine inspired by a Turing machine. In a Folding machine, the tape is finite, the data are integers and instead of having the functionality of the original Turing machine,
this machine uses folding tape operations. To perform a folding operation, the machine chooses a position between adjacent cells and folds the tape, adding the values of overlapping cells. Notice that the machine can also fold the tape before the tape center, as shown in the next figure. The machine can also choose to fold at the tape start or at the tape end, actually inverting the tape. Science of Bends Company is developing commercial versions of their Folding machine and its production have recently raised. The last lot produced, unfortunately, have some issues and some machines aren’t working properly. Some additional testing is therefore needed, to avoid selling defective machines, which would denigrate the company’s image. To test these machines, a set of tests and tapes are given. For each tape, the machine returns some computation result. Therefore, the engineers responsible for testing take note of the results and can verify if they are correct. But these engineers forgot to take note of which computation was made in each test case. To avoid re-testing all machines again, the engineers agreed that any combination of foldings is sound and accepted if, from a given input, it generates the expected output. You were hired to develop a program which, given the input and output tapes, determines whether there is a folding sequence that, starting from the input tape, generates the output tape.
【Input】
The input contains four lines. The first two lines refer to the input tape for the Folding machine and the last two lines refer to the output tape. The first line contains a single number, N, describing the input tape size. The second line contains N integers v1…vN describing the content of the input tape. The third line contains a single integer M, the output tape size; and the fourth line contains M integers w1…wM, the content of the output tape.
【Output】
You program must produce a single line, containing a single character, which must be "S" if there is a folding sequence able to generate the output tape starting from the input tape, and "N" otherwise.
【題目大意】
一條紙帶上許多格子，從某處對折后貼在一起的格子內(nèi)的數(shù)字可以相加专筷。在折疊過后紙帶可以不展開的前提下繼續(xù)折疊∪踉簦現(xiàn)在給初始紙帶狀態(tài)和最終狀態(tài)，問能否通過折疊得到最終狀態(tài)磷蛹，輸出是S否N吮旅。
【分析】
暴力搜索從哪里開始疊
typedef long long LL;
LL b[20];int m; bool bk;
void dfs(LL a[],int t) {
if (bk) return; if (t
if (t==m) {
bool bo=true;
for (int i=1;i<=m;i++) if (b[i]!=a[i]) {bo=false;break;}
if (bo) bk=true;
bo=true;
for (int i=1;i<=m;i++) if (b[i]!=a[t-i+1]) {bo=false;break;}
if (bo) bk=true;
return;
}
LL c[20];
for (int i=1;i
if (i*2
for (int j=1;j<=t-i;j++) {
if (j<=t-i*2) c[j]=a[t-j+1];
else c[j]=a[t-j+1]+a[2*i-t+j];
}
dfs(c,t-i);
}else {
for (int j=1;j<=i;j++) {
if (j<=2*i-t) c[j]=a[j];
else c[j]=a[j]+a[2*i-j+1];
}
dfs(c,i);
}
}
}
int main(){
int i,n;LL a[20]; bk=false;
scanf("%d",&n); for (i=1;i<=n;i++) scanf("%I64d",&a[i]);
scanf("%d",&m); for (i=1;i<=m;i++) scanf("%I64d",&b[i]);
dfs(a,n); if (bk) printf("S\n"); else printf("N\n");
return 0;
}
=================================================================
【Problem E-Dangerous Dive】
【Description】 The recent earthquake in Nlogonia did not affect too much the buildings in the capital, which was at the epicenter of the quake. But the scientists found that it affected the dike wall, which now has a significant structural failure in its underground part that, if not repaired quickly, can cause the
collapse of the dike, with the consequent flooding the whole capital.
The repair must be done by divers, at a large depth, under extremely difficult and dangerous
conditions. But since the survival of the city is at stake, its residents came out in large numbers to
volunteer for this dangerous mission.
As is traditional in dangerous missions, each diver received at the start of his/her mission a small
card with an identification number. At the end of their mission, the volunteers returned the nameplate,
placing it in a repository.
The dike is safe again, but unfortunately it seems that some volunteers did not return from their
missions. You were hired for the grueling task of, given the plates placed in the repository, determine
which volunteers lost their lives to save the city.
Input
The input is composed of two lines. The first line contains two integers N and R, indicating respectively
the number of volunteers that went to the mission and the number of volunteers that returned from
the mission. Volunteers are identified by numbers from 1 to N. The second line contains R integers,
indicating the volunteers which returned from the mission (at least one volunteer returned).
Output
Your program must produce a single line containing the identifiers of the volunteers who did not
return from their missions, in ascending order of their identifications. Leave a blank space after each
identifier (notice that, therefore, there must be a blank space after the last identifier in the line). If
every volunteer returned, the line must contain a single character ‘*’ (asterisc).
【題目大意】
地震志愿者blahblah，輸出沒來的志愿者多少個味咳。
【分析】
模擬
Waiting for complement;
bool bk[maxn];
int main(){
int n,m,i,x,cnt;
memset(bk,false,sizeof(bk));
scanf("%d%d",&n,&m);cnt=n;
for (i=1;i<=m;i++){
scanf("%d",&x);
bk[x]=true;cnt--;
}
if (cnt==0) printf("*\n");
else{
for (i=1;i<=n;i++)
if (bk[i]==false){
cnt--;
if (cnt) printf("%d ",i);
else {printf("%d \n",i);break;}
}
}
return 0;
}
=================================================================
【Problem F-Triangles】
【Description】You will be given N points on a circle. You must write a program to determine how many distinct equilateral triangles can be constructed using the given points as vertices.
【Input】
The first line of the input contains an integer N, the number of points given. The second line contains N integers Xi, representing the lengths of the circular arcs between two consecutive points in the circle: for 1 ≤ i ≤ (N ? 1), Xi represents the length of the arc between between points i and i + 1; XN represents the length of the arc between points N and 1.
【Output】
Your program must output a single line, containing a single integer, the number of distinct equilateral triangles that can be constructed using the given points as vertices.
【題目大意】
圓上n個點庇勃，選取三個作為三角形，問不同的選取方案之間是全等的三角形方案數(shù)有多少個槽驶。
【分析】
前綴和
int n,ans,bian;
int x[112345];
bool vis[112345]={0};
void judge(int m){
int sum=0,r=m;
while(r<=n) {
if(sum==bian) {ans++; vis[m]=1; }
if(sum>bian) break;
sum+=x[r++];
}
}
int main(){
int left=1,right=1,sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&x[i]);bian+=x[i]; }
if(bian%3){printf("0");return 0;}
bian/=3;
while(right<=n) {
if(vis[left]==1)break;
if(sum==bian)judge(right);
if(sum>bian) {sum-=x[left];left++;continue;}
sum+=x[right++];
}
printf("%d",ans);
}
=================================================================
【Problem G-Lines of Containers】
【Description】A shipment of Nlogs, the main export product from Nlogonia, is in the harbour, in containers, ready to be shipped. All containers have the same dimensions and all of them are cubes. Containers are organized in the cargo terminal in L lines and C columns, for a total of LC containers. Each container is marked with a distinct identification number, from 1 to LC. Each one of the L container lines will be loaded in a different ship. To make it simpler when unloading at each destination country, containers from a line must be organized such that the identifiers are in sequential order. More precisely, the first line must have the containers identified from 1 to C in increasing order, line 2 must have containers numbered from C + 1 to 2C (in increasing order), and so on until the last line. which will have containers numbered (L?1)C + 1 to LC (again, in increasing order). A crane is able to move either a full line or a full column of containers. It cannot move other groupments or individual containers. In night before the loading, a group of workers operated the cranes to swap shipment lines and columns as a way of protest because of low salaries. The loading must be done today, but before starting the containers must be reorganized as described previously. You must write a program which, given the information about the position of every container after the protest, determines whether you can reposition the containers in such way that every one of them is in its expected positions, using only cranes. If repositioning is possible, you must also calculate the smallest number of column and line swaps needed to do it.
【Input】 The first line of input contains two integers L and C which describe, respectively, the number of lines and columns of the shipment. The next L lines show the configuration of the containers after the workers protest. Each of these L lines will have C integers Xl;c indicating the position of a container. Every integer between 1 and LC appears exactly once in the input.
【Output】 Your program must produce a single line, containing a single integer, the minimum number of column and line swaps needed to place the containers in their original positions. If there is no way to place the containers in their original positions using only cranes, the line must contain only the character ‘*’.
【題目大意】
一個按先行后列順序填1~LC的LC矩陣责嚷，可以行交換，列交換掂铐。給出變化后的最終狀態(tài)罕拂，問最少幾步達到揍异，不能輸出*。
【分析】
分析爆班，未交換時衷掷，第i行的元素為(i-1)C+1 到 iC喧兄，第j列的元素%c都是定值浩姥，行交換時，同列的元素順序僅在列之內(nèi)變化答朋，不會破壞%c定值的特性碗旅。列交換時渡处，同行元素順序僅在同行內(nèi)變化，不會破壞區(qū)間所屬的性質(zhì)祟辟。檢查矩陣是否滿足上述兩個條件医瘫，最后答案轉(zhuǎn)化成行交換多少次，列交換多少次旧困。模擬即可醇份。
int main(){
int L,C;
int mat[311][311];
scanf("%d %d",&L,&C);
for(int i=1;i<=L;i++){
for(int j=1;j<=C;j++){
scanf("%d",&mat[i][j]);
if( (1+(mat[i][1]-1)/C) !=
(1+(mat[i][j]-1)/C) ){
cout<<"*";return 0;
}
}
}
for(int j=1;j<=C;j++)
for(int i=1;i<=L;i++)
if(mat[i][j]%C!=mat[1][j]%C){
cout<<"*";return 0;
}
int he[400];
for(int i=1;i<=C;i++) he[i]=1+((mat[1][i]-1)%C);
int ans=0;
bool flag=true;
while(1){
int i,j;
for(i=1;i<=C;i++) if(he[i]!=i) break;
if(i>C) break;
for(j=1;j<=C;j++) if(he[j]==i) break;
swap(he[j],he[i]);
ans++;
}
for(int i=1;i<=L;i++) he[i]=1+(mat[i][1]-1)/C;
while(1){
int i,j;
for(i=1;i<=L;i++) if(he[i]!=i) break;
if(i>L) break;
for(j=1;j<=L;j++) if(he[j]==i) break;
swap(he[j],he[i]);
ans++;
}
cout<<ans;
return 0;
}
=================================================================
【Problem H-Buses】
【Description】Programming competitions usually require infrastructure and organization on the part of those responsible. A problem that frequently must be solved is regarding transportation. While participating in a recent competition, Ricardinho watched the buses and micro-buses used in the transportation of competitors, all lined up one behind the other as competitors disembarked. The vehicles were all from the same company, although had different paintings. Ricardinho began to wonder how many ways that line could be formed using buses and minibuse from that company. Each bus is 10 meters long, each minibus is 5 meters long. Given the total length of a line of buses and minibuses, and the number of different colors each buse or minibus may be painted, Ricardinho wants to know in how many ways such a line can be formed.
【Input】 The input contains a single line, containing three integers N; K and L, representing respectively the total length, in meters, of the line Ricky is considering, K indicates the number of different colors for micro-buses, and L represents the number of different colors for buses. Note that, as integers N, K and L may be very large, the use of 64 bits integers is recommended.
【Output】 As the number of different ways of forming the line can be very large, Ricardinho is interested in the last 6 digits of that quantity. Thus, your program should produce a single line containing exactly 6 digits, corresponding to the last digits of the solution.
【題目大意】
長為5的倍數(shù)的路面停滿了巴士。2種巴士吼具，小巴5m長僚纷，大巴10米長。恰好停滿路面拗盒，不存在超出的情況怖竭。小巴有k種顏色，大巴有l(wèi)種顏色陡蝇，（k痊臭，l極大，longlong）現(xiàn)在問有多少種不同的停車方案登夫。同種車型的同種顏色如果交換位置認為是同一種方案广匙。答案輸出最后6位，不足補零恼策。
【分析】
dp鸦致。不妨把所有長度先除5，有長為n的路面上停1m的車或2m的車涣楷。設(shè)f[n]表示前n米停車方案數(shù)分唾，明顯有f[n]= f[n-1]k + f[n-2]l，即(n-1)+1m小車（k種） 和(n-2)+2m小車（L種）狮斗，由于n極大鳍寂，所以要矩陣快速冪來加速。設(shè)矩陣【Fn】=【fn情龄，fn-1】迄汛，則【Fn+1】=【fn+1捍壤，fn】，【Fn+1】=【Fn】【T】鞍爱，【T】是一個22 的矩陣鹃觉，為【（k），（1）睹逃；（L）盗扇，（0）】。
const int mod=1e6;
ll n,K,L;
struct node{
ll t[2][2];
}a,b;
node pp(node x,node y){
node r;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++){
r.t[i][j]=0;
for(int k=0;k<2;k++)
r.t[i][j]=(r.t[i][j]+x.t[i][k]*y.t[k][j])%mod;
}
return r;
}
void quickpow(ll m){
while(m) {
if(m&1)a=pp(a,b);
b=pp(b,b);
m=m>>1;
}
}
int main(){
scanf("%I64d%I64d%I64d",&n,&K,&L);
K=K%mod;L=L%mod;
b.t[0][0]=K;b.t[0][1]=1;
b.t[1][0]=L;b.t[1][1]=0;
n=n/5;
if(n==1)printf("I64d\n",K);
else if(n==2)printf("I64d\n",(K*K+L)%mod);
else {
a.t[0][0]=(K*K+L)%mod;
a.t[0][1]=K;
quickpow(n-2);
printf("I64d\n",a.t[0][0]%mod);
}
return 0;
}
=================================================================
【Problem I-Patches】
【Description】Carlos is very concerned with the environment. Whenever possible, he tries to use less polluting
means of transport. He recently got a job close to home and is now using his bike to go to work.
Unfortunately, in the route between his home and his job there is a nail factory, and often some
nails fall from their trucks, and end up puncturing Carlos’ bike tires. Therefore he ends up having to
make several patches on the tires of his bike.
To make the repairs, Carlos uses two different types of patches. Both types are as wide as a bike
tire, but differ in length. As the cost of the patch is proportional to its length, Carlos is trying to find
a way to save money, using the least possible length of patches to make the repairs, without cutting
the patches.
The first step in repairing a tire is making a chalk mark on a position of the tire and then writing
down the distances, measured clockwise, of each of the holes in relation to the chalk mark. Each hole
must be completely covered by a patch. Carl~ao would like your help to determine, given the positions
of the holes, the most economic way to make the repair.
【Input】
The input contains two lines. The first line contains four integers N; C; T1 e T2. Integer N indicates
the number of holes in the tire, and C indicates the cirunference length of the tire, in centimeters.
The lengths of the patches in centimeters are given by integers T1 and T2. The second line contains
N integers Fi, representing the distance, in clockwise direction, from the chalk mark to hole i, in
centimeters.
【Output】
Your program must print a single line, containing a single integer, the smallest total length of patches
needed to make all the repairs.
【題目大意】
輪胎上有一些洞需要修補沉填，現(xiàn)在按順時針順序給出洞在圓周上的弧長位置疗隶，給長度為T1,T2的兩種膠貼，問把所有洞填補最少要多長的膠貼翼闹。
【分析】
常見的dp問題斑鼻。f[i][j]表示填補前i個洞最后一個用膠貼j的最短長度。（j=0或1表示t1,t2）猎荠。明顯的坚弱，對于每一個i，找到膠貼j所能覆蓋到的最遠的洞关摇，進行更新即可荒叶。
int main(){
int n,c,t1,t2;
scanf("%d %d %d %d",&n,&c,&t1,&t2);
if(t1>t2) swap(t1,t2);
int hol[1010];
for(int i=1;i<=n;i++)scanf("%d",&hol[i]);
int f[1010][2];
for(int i=1;i<=n;i++){int k;
for(k=1;k<=i;k++) if(hol[k]+t1>=hol[i]) break;
f[i][0]=min(f[k-1][0]+t1,f[k-1][1]+t1);
for(k=1;k<=i;k++) if(hol[k]+t2>=hol[i]) break;
f[i][1]=min(f[k-1][0]+t2,f[k-1][1]+t2);
}
cout<<min(f[n][0],f[n][1]);
return 0;
}
=================================================================
【Problem J-Trucks】
【Description】The Subtle Balloons Company (SBC) is the main balloon provider for programming contests; it has
huge factories and warehouses, as well as an extensive truck fleet to ensure the contestants’ happiness.
There are lots of competition sites in Nlogonia, and all of them hired SBC for supplying balloons
for their contests. Nlogonia is an archipelago connected by several bridges. Every island of Nlogonia
may have several regional sites and may also house several SBC warehouses.
When planning the routes for balloon deliveries, SBC faced a problem: for safety issues, every
bridge in Nlogonia has some maximum weight limit for vehicles which cross it. And because of the
great net weight of the transported merchandise, SBC operations’ chief asked you to write a program
to determine the maximum weight allowed to be transported between warehouses and competition
sites.
【Input】
The first line contains three integers N, M and S which indicate, respectively, the number of islands,
the number of bridges that connect the islands and the number of sites. The islands are numbered
from 1 to N.
Each of the next M lines describes a bridge. The description of a bridge consists in a line with
three integers A, B and W , indicating respectively the two islands connected by the bridge and the
maximum weight allowed in that bridge, in tons.
All bridges are two-way roads; every pair of islands is connected by at most one bridge; and it is
possible to reach every other island in the archipelago using only bridges (naturally it may be needed
to pass through other islands to do so).
Each of the next S lines describe a competition site and contains two integers L and H indicating,
respectively, the number of the island where this site is and the number of the island where the
wharehouse which will be used to deliver the balloons to the site is.
【Output】
For each site in the input, in the order they were given, your program must produce a single line,
containing a single integer, the biggest weight which can be transported by truck from the warehouse
to the site.
【題目大意】
有n座島嶼（1~N），m個雙向橋梁输虱，保證任意兩個島嶼互達些楣。每架橋梁有限重，現(xiàn)在詢問某兩個島嶼之間一輛運輸貨物的卡車最多可載重多少貨物宪睹。換句話說戈毒，在N個點m條邊的無向連通圖，詢問某兩點之間的所有可達路徑上權(quán)值最小的邊的最大值横堡。
【分析】
每次看最小限重的一座橋梁（邊），如果去掉這條邊不影響整個圖的連通性冠桃，那么不管是哪兩個島嶼命贴，都不會從這條橋梁上經(jīng)過。（易證）食听。這樣直到最后的圖變成樹胸蛛，這樣任意兩個島嶼之間的路徑是唯一的，問題也變得簡單了樱报。然而葬项，刪除邊總是不容易操作，添加邊容易迹蛤，故做最大生成樹民珍。按邊權(quán)從大到小排序襟士，構(gòu)建生成樹。問題轉(zhuǎn)化為樹上兩個節(jié)點之間的路徑上權(quán)值最小是哪條邊嚷量。很明顯可以用最近公共祖先來處理陋桂，倍增法完成祖先信息，記gw[x][i]表示從x到其2^i的祖先的路徑上權(quán)值最小的邊蝶溶，這樣答案就可以很方便的得出了嗜历。
Waiting for complement;
define maxn 40001
define maxl 25
using namespace std;
typedef struct
{
int u,v,w;
}edge;//這個結(jié)構(gòu)體用來存儲邊
edge E[110000];
vectoredges;
vectorG[maxn];//保存邊的數(shù)組
int grand[maxn][maxl],gw[maxn][maxl];//x向上跳2i次方的節(jié)點，x到他上面祖先2i次方的距離
int depth[maxn];//深度
int n,m,N;
void addedge(int x,int y,int w){//把邊保存起來的函數(shù)
edge a={x,y,w},b={y,x,w};
edges.push_back(a);
edges.push_back(b);
G[x].push_back(edges.size()-2);
G[y].push_back(edges.size()-1);
}
void dfs(int x){//dfs建圖
for(int i=1;i<=N;i++){//第一個幾點就全部都是0咯抖所，第二個節(jié)點就有變化了梨州，不理解的話建議復(fù)制代碼輸出下這些數(shù)組
grand[x][i]=grand[grand[x][i-1]][i-1];
gw[x][i]=min(gw[x][i-1],gw[grand[x][i-1]][i-1]);
// if(grand[x][i]==0) break;
}
for(int i=0;i
edge e = edges[G[x][i]];
if(e.v!=grand[x][0]){//這里我們保存的是雙向邊所以與他相連的邊不是他父親就是他兒子父親的話就不能執(zhí)行，不然就死循環(huán)了田轧。
depth[e.v]=depth[x]+1;//他兒子的深度等于他爸爸的加1
grand[e.v][0]=x;//與x相連那個節(jié)點的父親等于x
gw[e.v][0]=e.w;//與x相連那個節(jié)點的距離等于這條邊的距離
dfs(e.v);//深搜往下面建
}
}
}
void Init(){
//n為節(jié)點個數(shù)
N = floor(log(n + 0.0) / log(2.0));//最多能跳的2^i祖先
depth[1]=0;//根結(jié)點的祖先不存在暴匠，用-1表示
memset(grand,0,sizeof(grand));
memset(gw,0x7f,sizeof(gw));
dfs(1);//以1為根節(jié)點建樹
// for(int i=1;i<=n;i++) cout<<depth[i]<<'+';cout<<endl;
}
int lca(int a,int b){
if(depth[a] > depth[b]) swap(a, b);//保證a在b上面，便于計算
int ans = 2147483647;
for(int i = N; i >= 0; i--) //類似于二進制拆分涯鲁，從大到小嘗試
if(depth[a] < depth[b] && depth[grand[b][i]] >= depth[a])//a在b下面且b向上跳后不會到a上面
ans =min(ans,gw[b][i]), b=grand[b][i];//先把深度較大的b往上跳
for(int j=N;j>=0;j--){//在同一高度了,他們一起向上跳,跳他們不相同節(jié)點巷查，當全都跳完之后grand[a][0]就是lca,上面有解釋哈。
if(grand[a][j]!=grand[b][j]) {
ans=min(ans,gw[a][j]); ans=min(ans,gw[b][j]);
a=grand[a][j]; b=grand[b][j];
}
}
// cout<<"="<<ans<<endl;
if(a!=b) { ans=min(ans,gw[a][0]); ans=min(ans,gw[b][0]); }
return ans;
}
int T[21000];
int cmp(const void *a,const void *b){
edge x=*(edge *)a;
edge y=*(edge *)b;
return x.w>y.w?-1:1;
}
int find(int x){
if(T[x]==x) return x;
else return T[x]=find(T[x]);
}
int main()
{
int q;
scanf("%d %d %d",&n,&m,&q);
for(int i=1;i<=m;i++) {
int x,y,w;
scanf("%d %d %d",&x,&y,&w);
E[i].u=x;E[i].v=y;E[i].w=w;
}
qsort(E+1,m,sizeof(E[1]),cmp);
for(int i=1;i<=n;i++) T[i]=i;
int cnt=n,i=1;
while(cnt>1){
//cout<<cnt<<endl;
int fu=find(E[i].u),fv=find(E[i].v);
if(fu!=fv) {
// cout<<E[i].u<<'='<<E[i].v<<' '<<E[i].w<<endl;
addedge(E[i].u,E[i].v,E[i].w);
T[fu]=fv;cnt--;
}
i++;
}
Init();
for(int i=1;i<=q;i++){
int x,y;
scanf("%d %d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
