作法 : DFS+二分搜尋+快速排序+DP
先說明一下為什麼要用二分搜尋+快速排序,由於第4筆測資的連接點太大
導致陣列沒辦法開太大(相鄰矩陣也是),而我...不會內建...也不會LINK LIST
(請不要趁我講的時候,想要跟我說這是什麼 我不會聽[跟LINK有仇])
所以才用如此複雜的辦法
程式碼1:只能拿到NA(80) 但是基本上想法是對的
程式碼2:能夠拿到AC 只不過,由於不斷的建出關係圖,以至於速度非常得慢
以下內容為想法介紹: 無耐心者自離
舉例此圖(用小畫家畫,畫不好請見諒)
以下為DFS搜樹其一的結果
接下來為跑法介紹: (小弟國文不好,請見諒)
1. 首先就是要利用DFS的特性,來建出一棵樹,建法不只有一種
2. 橘色代表可以回去的路,紅色代表呼叫的順序
3. 現在講解其一個跑法:
從起點(P1)開始,發現P2可以走,所以就走向P2(呼叫P2)
走到P2後,發現P3可以走,所以走向P3(呼叫P3)
走到P3後,發現P5可以走,所以走向P9(呼叫P9)
4. 此時走到P9,發現P9已經沒辦法繼續走下去了,可是我發現P9可以回到已經走過的點P3,因此此點的MIN=2(第2次呼叫的點),因此回傳MIN給P5
5. 此時退回到P5,發現P9這條分枝(P9為頭的一棵樹)的MIN=2,比P5所在的3還小,所以P9這條分枝上的點,不可能成為P5能擋掉的,此時P5也沒得走了,因此把MIN=2(讓P5為頭的一棵樹)能回到的最上層,回傳MIN給P3
6. 此時退回到P3,發現P5這條分枝(P5為頭的一棵樹)的MIN=2,>=該點的順序,所以代表P3可以阻擋P5這條分枝上的所有點,因此SUM累加分枝上的點個數(SUM=2),此時P3也沒點可以走,就要退回P2,P3因為可以回到P1(MIN=0),所以回傳的是0而不是2
7. 此時退回到P2,發現P3這條分枝(P5為頭的一棵樹)的MIN=0,<該點的順序,所以不累加P3這條分枝上的點,
由於DFS的特性,P2有點走了,必須走向P4(呼叫P4)
走到P4後,發現P6可以走,所以走向P6(呼叫P6)
走到P6後,發現P7可以走,所以走向P7(呼叫P7)
走到P8後,發現P8可以走,所以走向P8(呼叫P8)
8. 此時發現P8沒有辦法繼續走下去,回傳其MIN=6,(應該不用講了吧),退回P7
9. 退回P7後,由於<該點順序,不累加,回傳MIN=6,退回P6
10. 退回P6後,由於>=該點順序,代表P7這條分枝上的點個數(SUM+=2)可以防堵,回傳其MIN=6,退回P4
11. 退回P4後,由於>=該點順序,代表P6這條分枝上的點個數(SUM+=3)可以防堵,回傳其MIN=6,退回P2
12. 退回P2後,由於>=該點順序,代表P4這條分枝上的點個數(SUM+=4)可以防堵,由於P2沒點可以走,最後退回P1
13. 由於P1是起始點,且沒有點繼續走,所以不做比較,結束搜尋DFS
※ 起點不可過SUM+=的判斷
※ 快速累加該點以下的所有點順序,請用DP(d459: 一棵小樹),可以學習到
想法
※ SUM是累加的
※ 由於是DFS,因為它的特性,不會出現奇怪的道路!
※ DFS搜尋特性:有得走,就得走,沒得走,就退回上一個搜尋處
/********************************************************/
#include<stdlib.h>
#include<stdio.h>
short map[30001][1000]={0},maptop[30001]={0},V[30001]={0},ALL[30001]={0};
char used[30001]={0};
int MIN=2147483647,MINA;
int N,M,START,FIND;
int DFS(int now,int last,int time)
{
int a,back=2147483647,sum=0,appear[60001]={0};
V[now]=time;
FIND++;
/* printf("%d %d* :",now,maptop[now]);
for(a=0;a<maptop[now];a++) printf("%2d ",map[now][a]);
printf("\n");*/
for(a=0;a<maptop[now];a++)
if(used[map[now][a]]==0)
{
used[map[now][a]]=1;
int temp=DFS(map[now][a],now,time+1);
if(temp<back) back=temp;
if(temp>=V[now]&&now!=START)
{
sum+=ALL[map[now][a]];
}
}
else
{
if(V[map[now][a]]<back) back=V[map[now][a]];
}
if(N-sum<MIN||(N-sum==MIN&&now<MINA)) {MIN=N-sum;MINA=now;}
ALL[last]+=ALL[now];
return back;
}
main()
{
while(scanf("%d %d",&N,&M)==2)
{
int a,b,c,x,y;
for(a=1;a<=N;a++) {maptop[a]=0;used[a]=0;V[a]=0;ALL[a]=1;}
for(a=0;a<M;a++)
{
scanf("%d %d",&x,&y);
map[x][maptop[x]++]=y;
map[y][maptop[y]++]=x;
}
scanf("%d",&START);
used[START]=1;
MIN=2147483647,MINA,FIND=0;
DFS(START,0,1);
if(MIN==N) printf("0\n");
else printf("%d %d\n",MINA,MIN-(N-FIND));
}
return 0;
}
/**********************************************************/
#include<stdlib.h>
#include<stdio.h>
int V[30001],ALL[30001],px[60001],py[60001],ptime[30001]; /*px<->py連接*/
char used[30001]={0};
int MIN=2147483647,MINA;
int N,M,START,FIND;
int index1(int n,int M)
{
int lower=0, mid, high=M-1;
int index=-1;
do /*二分搜尋*/
{
mid=(lower+high)/2;
if(px[mid]<n) lower=mid+1;
else if(px[mid]>n) high=mid-1;
else index=mid;
}
while(index==-1&&lower<=high);
return index;
}
int DOp(int now,int M,int map[])
{
int INDEX=index1(now,M);
if(INDEX==-1) return 0;
else
{
int time=0,a;
for(a=INDEX;a<M;a++)
if(px[a]!=now) break;
else map[time++]=py[a];
for(a=INDEX-1;a>=0;a--)
if(px[a]!=now) break;
else map[time++]=py[a];
return time;
}
}
int DFS(int now,int last,int time)
{
int a,back=2147483647,sum=0,map[ptime[now]];
V[now]=time;
FIND++;
int pp=DOp(now,2*M,map);
for(a=0;a<pp;a++)
if(used[map[a]]==0)
{
used[map[a]]=1;
int temp=DFS(map[a],now,time+1);
if(temp<back) back=temp;
if(temp>=V[now]&&now!=START)
sum+=ALL[map[a]];
}
else
{
if(V[map[a]]<back&&map[a]!=last) back=V[map[a]];
}
if(N-sum<MIN||(N-sum==MIN&&now<MINA)) {MIN=N-sum;MINA=now;}
ALL[last]+=ALL[now];
return back;
}
int partition(int[], int, int);
void quicksort(int[], int, int);
main()
{
while(scanf("%d %d",&N,&M)==2)
{
int a,b,c,x,y;
for(a=1;a<=N;a++) {used[a]=0;V[a]=0;ALL[a]=1;ptime[a]=0;}
for(a=0;a<M;a++)
{
scanf("%d %d",&x,&y);
px[a]=x;py[a]=y;
px[M+a]=y;py[M+a]=x;
ptime[x]++;ptime[y]++;
}
quicksort(px,0,2*M-1);
scanf("%d",&START);
used[START]=1;
MIN=2147483647,MINA,FIND=0;
DFS(START,0,1);
if(MIN==N) printf("0\n");
else printf("%d %d\n",MINA,MIN-(N-FIND));
}
return 0;
}
int partition(int num[],int left,int right)
{
int a=left-1,b,s=num[right];
for(b=left;b<right;b++)
{
if(num[b]<s)
{
a++;
int temp;
temp=num[a];
num[a]=num[b];
num[b]=temp;
temp=py[a];
py[a]=py[b];
py[b]=temp;
}
}
int temp;
temp=num[a+1];
num[a+1]=num[right];
num[right]=temp;
temp=py[a+1];
py[a+1]=py[right];
py[right]=temp;
return a+1;
}
void quicksort(int num[],int left,int right)
{
int q;
if(left<right)
{
q=partition(num,left,right);
quicksort(num,left,q-1);
quicksort(num,q+1,right);
}
}
文章定位：
