有重邊,有自環(huán),卡精度.

View Code /* Source Code Problem: 1001 Username: 2010201211 Run Time: 304MS Memory: 1208K Language:C++ JudgeStatus: Accepted Author:MarkLiu */ #include <iostream> #include <algorithm> #include <cstdio> #include <stdio.h> #include <string.h> using namespace std;const int N = 201; const int INF = 1<<20; int n,d[N][N],kd[N][N],m; int g[N][N],gn[N]; double karp(){for(int i=0;i<=n;i++)for(int j=0;j<n;j++)kd[i][j]=INF;for(int i=0;i<n;i++)kd[0][i]=0;for(int i=1;i<=n;i++)for(int j=0;j<n;j++)if(kd[i-1][j]==INF) continue;else for(int k=gn[j]-1;k>=0;k--)kd[i][g[j][k]] = min(kd[i][g[j][k]],kd[i-1][j]+d[j][g[j][k]]);//cout << "debug" << endl;double minc=1e20;bool est=false;for(int i=0;i<n;i++){double mc=-1e20;if(kd[n][i]==INF) continue;for(int j=0;j<n;j++)if(kd[j][i]!=INF){mc=max(mc,1.0*(kd[n][i]-kd[j][i])/(n-j));est=true;}minc=min(minc,mc);}if(!est) minc=1e50;return minc; }int main(){//freopen("in.txt","r",stdin);int a,b,c;while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(i==j) d[i][j]=INF;else d[i][j]=INF;}while(m--){scanf("%d%d%d",&a,&b,&c);if(c<d[a-1][b-1])d[a-1][b-1]=c;}memset(g,0,sizeof(g));memset(gn,0,sizeof(gn));for(int i=0;i<n;i++){int cnt=0;for(int j=0;j<n;j++){if(d[i][j]!=0 && d[i][j]!=INF){g[i][cnt++]=j;}}gn[i]=cnt;}/*for(int i=0;i<n;i++){for(int j=0;j<gn[i];j++){printf("%d ",g[i][j]);}cout << endl;}*/double res=karp();if(res==1e50) printf("INF\n");else{printf("%.3lf\n",res+1e-9);}}return 0; } /* Sample Input: 3 3 1 2 2 2 3 2 3 1 1 8 7 1 1 14 8 1 969 5 3 518 3 5 948 7 2 962 8 2 221 1 1 935 3 3 2 3 2 3 2 2 1 1 1 Sample Output: 1.667 14.000 1.000 */

?

轉(zhuǎn)載于:https://www.cnblogs.com/markliu/archive/2012/06/05/2536434.html

總結(jié)

以上是生活随笔為你收集整理的2012黑龙江省赛J题-最小均值圈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。