http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2929

這個題一方面數據水，另一方面就是思維水，一拿到題就以為考最小生成樹。

因為這個題需要求各點間的距離，又因為豬圈的數目最大為600，所以根本就沒尋思考Floyd,一方面思維，另一方面是水的后臺，因為豬每天去固定的豬圈吃飯，所以求出每個豬到每個豬圈固定的距離便可。

WA（以為已經求出各點間的最短距離，只要豬圈沒豬便不會去）

反例

3 4 3

2

3

4

1 2 1

1 3 1

1 4 1

#include <iostream> #include <string.h> #include <stdlib.h> #include <stdio.h> #define N 1000001 using namespace std; int map[602][602],dis[602],v[602]; int n,m,k,a[401],V; void Floy() {for(int k=1; k<=m; k++){for(int j=1; j<=m; j++){for(int i=1; i<=m; i++){if(map[j][i]>map[j][k]+map[k][i]){map[j][i]=map[j][k]+map[k][i];}}}} } void prim() {memset(v,0,sizeof(v));for(int i=1; i<=m; i++)dis[i]=map[a[1]][i];v[a[1]]=1;int min,k;int sum=0;for(int i=1; i<V; i++){min=N;for(int j=1; j<=m; j++){if(v[j]==0&&dis[j]<min){min=dis[j];k=j;}}v[k]=1;//printf("min==%d\n",min);sum=sum+min;for(int j=1; j<=m; j++){if(v[j]==0&&dis[j]>map[k][j]){dis[j]=map[k][j];}}}printf("%d\n",sum); } int main() {int xx[1211],yy[1211],zz[1211];int sum,sum1;scanf("%d%d%d",&n,&m,&k);for(int i=1; i<=m; i++){for(int j=1; j<=m; j++){map[i][j]=N;map[j][i]=N;}map[i][i]=0;}int b[1211];V=0;memset(b,0,sizeof(b));for(int i=1; i<=n; i++){scanf("%d",&a[i]);b[a[i]]++;}for(int i=1; i<=m; i++){if(b[a[i]])V++;}for(int i=1; i<=k; i++){scanf("%d%d%d",&xx[i],&yy[i],&zz[i]);if(zz[i]<map[xx[i]][yy[i]]){map[xx[i]][yy[i]]=zz[i];map[yy[i]][xx[i]]=zz[i];}}Floy();/*for(int i=1;i<=m;i++){for(int j=1;j<=m;j++){printf("%d ",map[i][j]);}printf("\n");}*/for(int i=1; i<=k; i++){sum=0;sum1=0;for(int j=1; j<=n; j++){if(xx[i]==a[j]) sum++;if(yy[i]==a[j]) sum1++;}if(sum==0){for(int k=1; k<=m; k++){map[xx[i]][k]=N;map[k][xx[i]]=N;}map[xx[i]][xx[i]]=0;}if(sum1==0){for(int k=1; k<=m; k++){map[yy[i]][k]=N;map[k][yy[i]]=N;}map[yy[i]][yy[i]]=0;}if(sum&&sum1){map[xx[i]][yy[i]]=sum*map[xx[i]][yy[i]];map[yy[i]][xx[i]]=sum1*map[yy[i]][xx[i]];}}prim(); } return 0; }

AC的

#include <iostream> #include <string.h> #include <stdio.h> #include <stdlib.h> #define N 1000001 using namespace std; int n,m,k; int a[351],map[601][601]; void Floy() {for(int k=1; k<=m; k++){for(int i=1; i<=m; i++){for(int j=1; j<=m; j++){if(map[i][j]>map[i][k]+map[k][j]){map[i][j]=map[i][k]+map[k][j];}}}} } int main() {int xx,yy,zz;scanf("%d%d%d",&n,&m,&k);for(int i=1; i<=n; i++)scanf("%d",&a[i]);for(int i=1; i<=m; i++){for(int j=1; j<=m; j++){map[i][j]=N;map[j][i]=N;}map[i][i]=0;}while(k--){scanf("%d%d%d",&xx,&yy,&zz);if(map[xx][yy]>zz){map[xx][yy]=zz;map[yy][xx]=zz;}}Floy();int min=N;int sum;for(int i=1; i<=m; i++){sum=0;for(int j=1; j<=n; j++){sum=sum+map[a[j]][i];}if(min>sum)min=sum;}printf("%d\n",min); return 0; }

?

總結

以上是生活随笔為你收集整理的人活着系列之芳姐和芳姐的猪（Floyd）的全部內容，希望文章能夠幫你解決所遇到的問題。

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