[次短路徑]HAOI2005 路由選擇問題 route 解題報告

路由選擇問題

【問題描述】

    X城有一個含有N個節點的通信網絡，在通信中，我們往往關心資訊從一個節點I傳輸到節點J的最短路徑。遺憾的是，由於種種原因，線路中總有一些節點會出故障，因此在傳輸中要避開故障節點。

任務一：在己知故障節點的情況下，求避開這些故障節點，從節點I到節點J的最短路徑S0。

任務二：在不考慮故障節點的情況下，求從節點I到節點J的最短路徑S1、第二最短路徑S2。

【輸入文件】

第1行： N I J (節點個數 起始節點 目標節點)

第2—N+1行： Sk1 Sk2…SkN (節點K到節點J的距離爲SkJ K=1，2，……，N)

最後一行： P T1 T2……Tp (故障節點的個數及編號)

【輸出文件】

S0 S1 S2 (S1<=S2 從節點I到節點J至少有兩條不同路徑)

[並查集]HAOI 破譯密文 encrypt 解題報告

【題目描述】  查看題目
原文鏈接：http://yeefan.tk/blog/haoi-encrypt/
資訊的明文是由0利1組成的非空序列。但在網絡通信中，為了資訊的安全性，常對明文進行加密，用密文進行傳輸。密文是由0、1和若干個密碼字母組成，每個密碼字母代表不同的01串，例如，密文二011a0bf00a01。密碼破譯的關鍵是確定每個密碼的含義。
經過長期統計分析，現在知道了每個密碼的固定長度，如今，我方又截獲了敵方的兩段密文S1和S2，並且知道S1二S2，即兩段密文代表相同的明文。你的任務是幫助情報人員對給定的兩段密文進行分析，看一看有多少種可能的明文。
【輸入文件】
第1行： S1 (第1段密文)
第2行： S2 (第2段密文)
第3行： N (密碼總數， N<=26)
第4—N+3行： 字母i 長度i (密碼用小寫英文字母表示， 密碼長度<=100)

【輸出文件】
M（表示有M種可能的明文）

【輸入輸出樣例】
encrypt.in
100ad1
cc1
4
a 2
d 3
c 4
b 50
encrypt.out
2
【約束條件】
明文的長度<=10000

【分析】
既然每個密文代表一段明文,那我們可以把密文展開
如樣例的:
100ad1
cc1
4
a 2
d 3
c 4
b 50
我們就可以展開成
1 0 0 a1 a2 d1 d2 d3 1
c1 c2 c3 c4 c1 c2 c3 c4 1
那麼問題就成了在這麼一串數中找出有多少個數不定集合.
即c1代表1 c2代表0 c3代表0
但是 c4和a1共同代表什麼呢,這是問題的關鍵,這就用到了並查集:
首先 1 0 a1 a2…d2 d3都是獨立的集合
從i=1開始向右掃描
先把1所在的集合和c1所在的集合歸成一類,
0所在的集合和c2所在的集合歸成一類
….
最後一定是
代表0的字母有一個集合
代表1的字母有一個集合
不能確定代表什麼的有x個集合
因為每個集合代表的數字要麼是1要麼是0有兩種情況
所以兩個集合有4種情況
三個集合有8種情況
x個集合有2^x種情況
所以我們只需要用並查集算出有幾個非0或1的集合,再累乘後輸出即可
注意:有一個密文既對應0也對應1,這種情況構不成任何正確的明文,所以應當輸出0。

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
using namespace std;
int num[30];
 
const char base='a'-1;
const int MAXN=3000;
int Letter[30];//每個密碼的密碼長度
int Num[30][102];
char S1[105];
char S2[105];
int N;//密碼總數
int T=0;//不定集合的數量
int Sum=0;//最終結果
int M=0;
int DealA[MAXN]={0};
int DealB[MAXN]={0};
int Num0;
int Num1;
int Len=0;
 
class Node
{
public:
 int parent;
 int count;
}UFS[MAXN];
 
void UFS_Init(int i)
{
 UFS[i].count=1;
 UFS[i].parent=i;
}
 
int UFS_Find(int x)
{
 int i=x;
 while(i!=UFS[i].parent)
  i=UFS[i].parent;
 
 int j=x;
 while(j!=i)
 {
  int tmp=UFS[j].parent;
  UFS[j].parent=i;
  j=tmp;
 }
 return i;
}
 
void UFS_Merge(int x,int y)
{
 x=UFS_Find(x);
 y=UFS_Find(y);
 if(x==y)
  return;
 
 if(UFS[x].count>UFS[y].count)
 {
  UFS[y].parent=x;
  UFS[x].count+=UFS[y].count;
 }
 else
 {
  UFS[x].parent=y;
  UFS[y].count+=UFS[x].count;
 }
}
 
void init()
{
 scanf("%s\n%s\n",&S1,&S2);
 scanf("%d\n",&N);
 memset(Letter,0,sizeof(Letter));
 char cTmp;
 int iTmp;
 for (int i=1;i<=N;i++)
 {
  scanf("%c %d\n",&cTmp,&iTmp);
  Letter[cTmp-base]=iTmp;
 } 
 
 for(int i=1;i<=26;i++)
 {
  for (int j=1;j<=Letter[i];j++)
  {
   M++;
   Num[i][j]=M;
   UFS_Init(M);
  }
 }
 
 M++;
 Num0=M;
 UFS_Init(M);
 
 M++;
 Num1=M;
 UFS_Init(M);
 
 int top=0;
 for (unsigned int i=0;i<strlen(S1);i++)
 {
  if(isalpha(S1[i]))
  {
   for (int j=1;j<=Letter[ S1[i]-base ]; j++)
   {
    top++;
    DealA[top]=Num[S1[i]-base][j];
   }
  }
  else
  {
   if(S1[i]=='0')
   {
    top++;
    DealA[top]=Num0;
   }
   else
   {
    top++;
    DealA[top]=Num1;
   }
  }
 }
 
 Len=top;
 top=0;
 for (unsigned int i=0;i<strlen(S2);i++)
 {
  if(isalpha(S2[i]))
  {
   for (int j=1;j<=Letter[ S2[i]-base ]; j++)
   {
    top++;
    DealB[top]=Num[S2[i]-base][j];
   }
  }
  else
  {
   if(S2[i]=='0')
   {
    top++;
    DealB[top]=Num0;
   }
   else
   {
    top++;
    DealB[top]=Num1;
   }
  }
 } 
}
 
int work()
{
 for(int i=1;i<=Len;i++)
 {
  UFS_Merge(DealA[i],DealB[i]);
 }
 
 if(UFS_Find(Num0)==UFS_Find(Num1))
 {
  return 0;
 }
 
 bool Used[MAXN];
 memset(Used,0,sizeof(Used));
 
 int Find_Num0=UFS_Find(Num0);
 int Find_Num1=UFS_Find(Num1);
 for(int i=1;i<=Len;i++)
 { 
  int tmp=UFS_Find(DealA[i]);
  if(tmp==Find_Num0 || tmp==Find_Num1 || Used[tmp])
   continue;
 
  T++;
  Used[tmp]=true;
 }
 
 for(int i=1;i<=Len;i++)
 {
  int tmp=UFS_Find(DealB[i]);
  if(tmp==Find_Num0 || tmp==Find_Num1 || Used[tmp])
   continue;
 
  T++;
  Used[tmp]=true;
 }
 
 Sum=1;
 for (int i=1;i<=T;i++)
  Sum*=2;
 return Sum;
}
 
int main()
{
 freopen("encrypt.in","r",stdin);
 freopen("encrypt.out","w",stdout);
 init();
 printf("%d\n",work());
 return 0;
}

[圖論][最短路]HAOI：希望小學 hopeschool 解題報告

【問題描述】

地處偏僻山區的X鄉有N個自然村，目前還沒有一所小學，孩子們要麼不上學，要麼需要翻過一座大山到別處上學。如今好啦，有一位熱心人士準備捐款在某個自然村建立一所希望小學。

通過調查發現，X鄉各個村莊之間的道路較爲複雜，有平路、上坡和下坡。考慮到每個村孩子們的人數不同，走上坡、下坡和平路的速度也不同，男孩和女孩走路速度也不同，請你爲X鄉選擇一個最合適建立希望小學的村莊，使得所有的孩子花在路上的總時間最少。

【輸入文件】

hopeschool.in

第1行： N B1 B2 B3 G1 G2 G3 (村莊數、男孩分別走平路、上坡、下坡每千米花費的時間以及女孩分別走平路、上坡、下坡每千米花費的時間)

第2行： Xl X2……Xn (Xi表示第i個村要上學的男孩人數)

第3行： Y1 Y2……Yn (Yi表示第i個村要上學的女孩人數)

第4行： K (道路數)

第5—K+4行： Ai Bi Si1 Si2 Si3 (村莊Ai到村莊Bi，平路Sil千米，上坡Si2千米，下坡Si3千米,i=1,2,…，K)

【輸出文件】

hopeschool.out

T（將要建立希望小學村莊的編號）

【約束條件】

(1) N<=30， Xi<=20， Yi<=20

(2) K<=100， 每條路的長度<=30千米

(3) B1，B2，B3，G1，G2，G3爲整數，都小於10個單位時間／每千米

(4) 每條道路只給出一組數據。例如：5 8 7 10 3表示從村莊5往村莊8走，平路

有7千米，上坡10千米。 下坡3千米；當然也表示從村莊8往村莊5走，平路有7千米，

上坡3千米。下坡10千米。

【輸入輸出樣例】

hopeschool.in

2 2 2 1 2 3 2

10 12

5 4

1

1 2 10 2 1

hopeschool.out

2

【分析】 

最短路問題，由於節點很少，而且還是多源最短路，所以Floyd算法很合適。

 由於男孩、女孩的速度不一樣，所以要分開求最短路。最後枚舉每個村莊求最優解即可。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class Village
{
public:
    int s,e;
    int ping,up,down;
}V[203];
   
int Boy[31];
int Girl[31];
int Matb[31][31];
int Matg[31][31];
int N,K;
int B1,B2,B3;
int G1,G2,G3;

void init()
{
    scanf("%d %d %d %d %d %d %d\n",&N,&B1,&B2,&B3,&G1,&G2,&G3);
   
    for(int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            Matb[i][j]=-1,Matg[i][j]=-1;
   
    for (int i=1;i<=N;i++)
        Matg[i][i]=0,Matb[i][i]=0;
       
    for (int i=1;i<=N;i++)
        scanf("%d",&Boy[i]);
    for (int i=1;i<=N;i++)
        scanf("%d",&Girl[i]);
    scanf("%d\n",&K);
   
    for (int i=1;i<=K;i++)
    {
        scanf("%d %d %d %d %d\n",&V[i].s,&V[i].e,&V[i].ping,&V[i].up,&V[i].down);
        V[i+K].e=V[i].s;
        V[i+K].s=V[i].e;
        V[i+K].ping=V[i].ping;
        V[i+K].up=V[i].down;
        V[i+K].down=V[i].up;
    }
   
    int s,e;
    int t1;//人數
    int t2;//速度
    int t3;//路程
    int t4;//時間
    int t;//總時間
    for (int i=1;i<=K*2;i++)
    {
        t=0;
        s=V[i].s;
        e=V[i].e;
        t1=Boy[s];
        t2=B1;
        t3=V[i].ping;
        t4=t1*t3*t2;
        t+=t4;
       
        t2=B2;
        t3=V[i].up;
        t4=t1*t3*t2;
        t+=t4;
       
        t2=B3;
        t3=V[i].down;
        t4=t1*t3*t2;
        t+=t4;
        Matb[s][e]=t;
       
        t=0;
        t1=Girl[s];
        t2=G1;
        t3=V[i].ping;
        t4=t1*t3*t2;
        t+=t4;
       
        t2=G2;
        t3=V[i].up;
        t4=t1*t3*t2;
        t+=t4;
       
        t2=G3;
        t3=V[i].down;
        t4=t1*t3*t2;
        t+=t4;
        Matg[s][e]=t;
    }
}
void Floydb()
{
    int temp;
    for (int k=1;k<=N;k++) 
    { 
        for(int i=1;i<=N;i++) 
        { 
            for(int j=1;j<=N;j++) 
            { 
                if ( Matb[i][k]!=-1 && Matb[k][j]!=-1) 
                { 
                    temp=Matb[i][k]+Matb[k][j];
                    if ( (Matb[i][j]==-1) || ( Matb[i][j]>temp ) ) 
                        Matb[i][j]=temp; 
                } 
            } 
        } 
    } 
}

void Floydg()
{
    int temp;
    for (int k=1;k<=N;k++) 
    { 
        for(int i=1;i<=N;i++) 
        { 
            for(int j=1;j<=N;j++) 
            { 
                if ( Matg[i][k]!=-1 && Matg[k][j]!=-1) 
                { 
                    temp=Matg[i][k]+Matg[k][j];
                    if ( (Matg[i][j]==-1) || ( Matg[i][j]>temp ) ) 
                        Matg[i][j]=temp; 
                } 
            } 
        } 
    } 
}

void Search()
{
    int Minn=200000000;
    int Minx=0;
    for (int i=1;i<=N;i++)
    {
        int t=0;
        for (int j=1;j<=N;j++)
            t=t+Matg[j][i]+Matb[j][i];
        if(t<Minn)
        {
            Minn=t;
            Minx=i;
        }
    }
    printf("%d\n",Minx);
}

int main()
{
    freopen("hopeschool.in","r",stdin);
    freopen("hopeschool.out","w",stdout);
    init();
    Floydb();
    Floydg();
    Search();
    return 0;
}

【評測結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	20	0.000 s	284 KB	0
2	正确	20	0.000 s	284 KB	0
3	正确	20	0.000 s	284 KB	0
4	正确	20	0.000 s	284 KB	0
5	正确	20	0.001 s	284 KB	0

运行完成
运行时间 0.002 s
平均内存使用 284 KB
测试点通过状况 AAAAA
得分：100
恭喜你通过了全部测试点!

[貪心策略]HAOI ：巧克力 chocolate 解題報告

試題描述

有一塊n*m的矩形巧克力，準備將它切成n*m塊。巧克力上共有n-1條橫綫和m-1條豎綫，你每次可以沿着其中的一條橫綫或豎綫將巧克力切開，無論切割的長短，沿着每條橫綫切一次的代價依次爲y1，y2，…，yn-1，而沿豎綫切割的代價依次爲x1，x2，…，xm-1。例如，對於下圖6*4的巧克力，我們先沿着三條橫綫切割，需要3刀，得到4條巧克力，然後再將這4條巧克力沿豎綫切割，每條都需要5刀，則最終所花費的代價爲y1+y2+y3+4*(x1+x2+x3+x4+x5)。

當然，上述簡單切法不見得是最優切法，那麼怎樣切割該塊巧克力，花費的代價最少呢？

輸入數據

第一行爲兩個整數n和m。

接下來n-1行，每行一個整數，分別代表x1，x2，…，xn-1。

接下來m-1行，每行一個整數，分別代表y1，y2，…，ym-1。

輸出數據

輸出一整數，爲切割巧克力的最小代價。

樣例輸入

6 4

2

1

3

1

4

4

1

2

樣例輸出

42

測試數據範圍

30%的數據，n<=100,m<=100

100%的數據，n<=10000，m<=10000

【分析】

貪心策略，先快速排序一下，不管橫豎，選擇最大的先切（有相等無所謂，當有幾個相等的最大值時，隨便選一個即可）。

【我的代碼】

 #include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int X[10001];
int Y[10001];

int Nx,Ny;

int cmp(const void *a,const void *b)
{
    return *((int *)b)-*((int *)a);
}

void init()
{
    scanf("%d %d\n",&Nx,&Ny);

    for (int i=1;i<=Nx-1;i++)
        scanf("%d\n",&X[i]);
    for (int i=1;i<=Ny-1;i++)
        scanf("%d\n",&Y[i]);
  
    qsort(X+1,Nx-1,sizeof(X[0]),cmp);
    qsort(Y+1,Ny-1,sizeof(Y[0]),cmp);
    return;
}


void greedy()
{
    int Tx=1,Ty=1;
    int ge=0;
    int tot=Nx+Ny-2;
    int T=0;
    while(ge<tot)
    {
        if(X[Tx]>=Y[Ty])
        {
            T+=(X[Tx]*Ty);
            Tx++;
            ge++;
            continue;
        }
        T+=(Y[Ty]*Tx);
        Ty++;
        ge++;
    }
    printf("%d\n",T);
}

int main()
{
    freopen("chocolate.in","r",stdin);
    freopen("chocolate.out","w",stdout);
    init();
    greedy();
    return 0;
}