?

Description

?

Input

數據的第1行為兩個整數N和E，以空格分隔，分別表示森林中的景點數和連接相鄰景點的路的條數。 第2行包含兩個整數C和M，以空格分隔，分別表示初始時聰聰和可可所在的景點的編號。 接下來E行，每行兩個整數，第i+2行的兩個整數Ai和Bi表示景點Ai和景點Bi之間有一條路。 所有的路都是無向的，即：如果能從A走到B，就可以從B走到A。 輸入保證任何兩個景點之間不會有多于一條路直接相連，且聰聰和可可之間必有路直接或間接的相連。

Output

輸出1個實數，四舍五入保留三位小數，表示平均多少個時間單位后聰聰會把可可吃掉。

Sample Input

【輸入樣例1】
4 3
1 4
1 2
2 3
3 4
【輸入樣例2】
9 9
9 3
1 2
2 3
3 4
4 5
3 6
4 6
4 7
7 8
8 9

Sample Output

【輸出樣例1】
1.500
【輸出樣例2】
2.167

HINT

【樣例說明1】
開始時，聰聰和可可分別在景點1和景點4。
第一個時刻，聰聰先走，她向更靠近可可(景點4)的景點走動，走到景點2，然后走到景點3；假定忽略走路所花時間。
可可后走，有兩種可能：
第一種是走到景點3，這樣聰聰和可可到達同一個景點，可可被吃掉，步數為1，概率為 。
第二種是停在景點4，不被吃掉。概率為 。
到第二個時刻，聰聰向更靠近可可(景點4)的景點走動，只需要走一步即和可可在同一景點。因此這種情況下聰聰會在兩步吃掉可可。
所以平均的步數是1* +2* =1.5步。

對于所有的數據，1≤N,E≤1000。
對于50%的數據，1≤N≤50。

?

solution：

先預處理出來一個表f[i][j]，表示聰聰在i時，可可在j時，聰聰走一步時的最優 (我一開始處理了一個走一步和兩步一共的最優，是錯誤的，因為有的奇怪情況會..)為了處理這個表，可以用n遍spfa， 網上大神說這是個稀疏圖，稀疏圖用spfa比較快然后就是記憶化dfs(感覺最近dfs用的有點多)，一定要記憶化，否則會超3個點 int kk=f[f[i][j]][j] 設temp為與j相連的點 dp[i][j]=1+(sigma(dp[kk][temp])+dp[kk][j])/(1+outdegree[j]); 1的意思是從i走到kk (sigma(dp[kk][temp])+dp[kk][j])枚舉可可的幾種情況，并且聰聰先走 (1+outdegree[j])就是概率


1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<queue> 5 #include<algorithm> 6 #include<ctime> 7 #define dd double 8 #define mem(a,b) memset(a,b,sizeof(a)) 9 using namespace std; 10 int maxn(int a,int b){return a>b?a:b;} 11 int minn(int a,int b){return a<b?a:b;} 12 struct son 13 { 14 int v,next; 15 }; 16 son a1[2001]; 17 int first[2001],e; 18 19 void addbian(int u,int v) 20 { 21 a1[e].v=v; 22 a1[e].next=first[u]; 23 first[u]=e++; 24 } 25 26 double outdegree[2001]; 27 double gai[2001]; 28 int f[2001][2001];//貓在i 老鼠在j時 下一步的選擇 29 30 double ans; 31 32 int n,m,kk,cc; 33 int u,o,p; 34 int vis[2001]; 35 struct son1 36 { 37 int val,order; 38 }; 39 queue<int> q; 40 int d[2001][2001]; 41 double dp[2001][2001]; 42 43 void dfs(int cc,int kk) 44 { 45 //printf("cc=%d kk=%d bushu=%d gailu=%.19lf\n",cc,kk,bushu,gailu); 46 if(dp[cc][kk]) 47 return ; 48 if(cc==kk)//可可自己送上門來 49 { 50 //ans+=(dd)bushu*gailu; 51 dp[cc][kk]=0; 52 return ; 53 } 54 if(f[cc][kk]==kk||f[f[cc][kk]][kk]==kk)//聰聰先走，吃了可可 55 { 56 //ans+=(dd)(bushu+1)*gailu; 57 dp[cc][kk]=1; 58 return ; 59 } 60 dfs(f[f[cc][kk]][kk],kk); 61 dp[cc][kk]+=dp[f[f[cc][kk]][kk]][kk]; 62 for(int i=first[kk];i!=-1;i=a1[i].next) 63 { 64 int temp=a1[i].v; 65 dfs(f[f[cc][kk]][kk],temp); 66 dp[cc][kk]+=dp[f[f[cc][kk]][kk]][temp]; 67 } 68 dp[cc][kk]/=(1.0+(dd)outdegree[kk]); 69 dp[cc][kk]+=1.0; 70 return ; 71 } 72 73 int spfa(int x) 74 { 75 mem(vis,0); 76 mem(d[x],0x7f/3); 77 vis[x]=1; 78 q.push(x); 79 d[x][x]=0; 80 while(!q.empty()) 81 { 82 int k=q.front(); 83 vis[k]=0; 84 q.pop(); 85 for(int i=first[k];i!=-1;i=a1[i].next) 86 { 87 int temp=a1[i].v; 88 if(d[x][temp]>d[x][k]+1) 89 { 90 d[x][temp]=d[x][k]+1; 91 if(!vis[temp]) 92 { 93 q.push(temp); 94 vis[temp]=1; 95 } 96 } 97 } 98 } 99 } 100 101 102 void SPFA() 103 { 104 for(int i=1;i<=n;++i) 105 spfa(i); 106 107 int minl,order; 108 for(int k=1;k<=n;++k) 109 for(int i=1;i<=n;++i) 110 { 111 minl=d[i][k];order=i; 112 for(int j=first[i];j!=-1;j=a1[j].next) 113 { 114 int temp=a1[j].v; 115 if(d[temp][k]==minl) 116 order=minn(order,temp); 117 else 118 if(d[temp][k]<minl) 119 { 120 minl=d[temp][k]; 121 order=temp; 122 } 123 } 124 f[i][k]=order; 125 } 126 } 127 128 void out11() 129 { 130 printf("\n"); 131 for(int i=1;i<=n;++i) 132 { 133 for(int j=1;j<=n;++j) 134 printf("%d ",d[i][j]); 135 printf("\n"); 136 } 137 printf("\n"); 138 for(int i=1;i<=n;++i) 139 { 140 for(int j=1;j<=n;++j) 141 printf("%d ",f[i][j]); 142 printf("\n"); 143 } 144 printf("\n"); 145 /*for(int i=1;i<=n;++i) 146 { 147 for(int j=1;j<=n;++j) 148 printf("%.3lf ",dp[i][j]); 149 printf("\n"); 150 } 151 printf("\n");*/ 152 } 153 154 int main(){ 155 //freopen("1.txt","r",stdin); 156 freopen("cchkk.in","r",stdin); 157 freopen("cchkk.out","w",stdout); 158 //freopen("3.txt","w",stdout); 159 mem(first,-1); 160 scanf("%d%d%d%d",&n,&m,&cc,&kk); 161 for(int i=1;i<=m;++i) 162 { 163 scanf("%d%d",&u,&o); 164 ++outdegree[u]; 165 ++outdegree[o]; 166 addbian(u,o); 167 addbian(o,u); 168 } 169 SPFA(); 170 //printf("time=%d\n",clock()); 171 for(int i=1;i<=n;++i) 172 gai[i]=1.0/(outdegree[i]+1.0); 173 //cout<<0; 174 dfs(cc,kk); 175 //out11(); 176 //printf("%.3lf",dp[cc][kk]); 177 printf("%.3lf",dp[cc][kk]); 178 //while(1); 179 return 0; 180 } View Code

?

1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<queue> 5 #include<algorithm> 6 #include<ctime> 7 #define dd double 8 #define mem(a,b) memset(a,b,sizeof(a)) 9 using namespace std; 10 int maxn(int a,int b){return a>b?a:b;} 11 int minn(int a,int b){return a<b?a:b;} 12 struct son 13 { 14 int v,next; 15 }; 16 son a1[2001]; 17 int first[2001],e; 18 19 void addbian(int u,int v) 20 { 21 a1[e].v=v; 22 a1[e].next=first[u]; 23 first[u]=e++; 24 } 25 26 double outdegree[2001]; 27 double gai[2001]; 28 int f[2001][2001];//貓在i 老鼠在j時 下一步的選擇 29 30 double ans; 31 32 int n,m,kk,cc; 33 int u,o,p; 34 int vis[2001]; 35 struct son1 36 { 37 int val,order; 38 }; 39 queue<int> q; 40 int d[2001][2001]; 41 42 void dfs(int cc,int kk,int bushu,double gailu) 43 { 44 //printf("cc=%d kk=%d bushu=%d gailu=%.3lf\n",cc,kk,bushu,gailu); 45 if(cc==kk)//可可自己送上門來 46 { 47 ans+=(dd)bushu*gailu; 48 return ; 49 } 50 if(f[cc][kk]==kk||f[f[cc][kk]][kk]==kk)//聰聰先走，吃了可可 51 { 52 ans+=(dd)(bushu+1)*gailu; 53 return ; 54 } 55 56 dfs(f[f[cc][kk]][kk],kk,bushu+1,gailu*gai[kk]); 57 //dp[cc][kk]+=dp[f[cc][kk]][kk]; 58 for(int i=first[kk];i!=-1;i=a1[i].next) 59 { 60 int temp=a1[i].v; 61 dfs(f[f[cc][kk]][kk],temp,bushu+1,gailu*gai[kk]); 62 //dp[cc][kk]+=dp[f[cc][kk]][temp]; 63 } 64 //dp[cc][kk]/=(1.0+(dd)outdegree[kk]); 65 //dp[cc][kk]+=1.0; 66 } 67 68 int spfa(int x) 69 { 70 mem(vis,0); 71 mem(d[x],0x7f/3); 72 vis[x]=1; 73 q.push(x); 74 d[x][x]=0; 75 while(!q.empty()) 76 { 77 int k=q.front(); 78 vis[k]=0; 79 q.pop(); 80 for(int i=first[k];i!=-1;i=a1[i].next) 81 { 82 int temp=a1[i].v; 83 if(d[x][temp]>d[x][k]+1) 84 { 85 d[x][temp]=d[x][k]+1; 86 if(!vis[temp]) 87 { 88 q.push(temp); 89 vis[temp]=1; 90 } 91 } 92 } 93 } 94 } 95 96 97 void SPFA() 98 { 99 for(int i=1;i<=n;++i) 100 spfa(i); 101 102 int minl,order; 103 for(int k=1;k<=n;++k) 104 for(int i=1;i<=n;++i) 105 { 106 minl=d[i][k];order=i; 107 for(int j=first[i];j!=-1;j=a1[j].next) 108 { 109 int temp=a1[j].v; 110 if(d[temp][k]==minl) 111 order=minn(order,temp); 112 else 113 if(d[temp][k]<minl) 114 { 115 minl=d[temp][k]; 116 order=temp; 117 } 118 } 119 f[i][k]=order; 120 } 121 } 122 123 void out11() 124 { 125 printf("\n"); 126 for(int i=1;i<=n;++i) 127 { 128 for(int j=1;j<=n;++j) 129 printf("%d ",d[i][j]); 130 printf("\n"); 131 } 132 printf("\n"); 133 for(int i=1;i<=n;++i) 134 { 135 for(int j=1;j<=n;++j) 136 printf("%d ",f[i][j]); 137 printf("\n"); 138 } 139 printf("\n"); 140 /*for(int i=1;i<=n;++i) 141 { 142 for(int j=1;j<=n;++j) 143 printf("%.3lf ",dp[i][j]); 144 printf("\n"); 145 } 146 printf("\n");*/ 147 } 148 149 int main(){ 150 //freopen("1.txt","r",stdin); 151 freopen("cchkk.in","r",stdin); 152 freopen("cchkk.out","w",stdout); 153 //freopen("3.txt","w",stdout); 154 mem(first,-1); 155 scanf("%d%d%d%d",&n,&m,&cc,&kk); 156 for(int i=1;i<=m;++i) 157 { 158 scanf("%d%d",&u,&o); 159 ++outdegree[u]; 160 ++outdegree[o]; 161 addbian(u,o); 162 addbian(o,u); 163 } 164 SPFA(); 165 //printf("time=%d\n",clock()); 166 for(int i=1;i<=n;++i) 167 gai[i]=1.0/(outdegree[i]+1.0); 168 //cout<<0; 169 dfs(cc,kk,0,1.0); 170 //out11(); 171 //printf("%.3lf",dp[cc][kk]); 172 printf("%.3lf",ans); 173 //while(1); 174 return 0; 175 } 暴力

?

轉載于:https://www.cnblogs.com/A-LEAF/p/7247453.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的聪聪和可可的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。