抖音网站,网站空间怎么更换,wordpress tag生成的链接乱,建设企业银行网站http://poj.org/problem?id3621 这两天一直在复习代码#xff0c;因为好久都不写东西了#xff0c;而且转了语言#xff0c;除了Dinic我什么都不会写…… 题目大意#xff1a;给你一个有向图#xff0c;边有权#xff08;T#xff09;#xff0c;点有权#xff08;F3621 这两天一直在复习代码因为好久都不写东西了而且转了语言除了Dinic我什么都不会写…… 题目大意给你一个有向图边有权T点有权F使求一个环使得最大化∑(F)/∑(T)。 这是一个最优比率环问题与上一个最有比率生成树问题相似都是01分数规划的考点。 设 ans≥∑(F)/∑(T) , 有 ∑(F)-∑(T)*ans≤0 ∑(F-T*ans)≤0 我们可以二分ans将图的边权变为 F-T*ans用SPFA判断图中是否有负权回路。如果图中有负权回路则当前回路中 ∑(F)-∑(T)*ans0,继而推得∑(F)/∑(T)≤ans,为符合条件的解ans需要向上二分反之ans需要向下二分。 难看的代码: #include iostream
#include cstdio
#include cstring
#include cstdlib
#include queue
#include cmath
#define DINF 10000000.0
#define mm 10000
#define mn 1001
#define eps 1e-3
using namespace std;queueint q;
int x,y,n,m,cnt[mn];
double dist[mn],F[mn],z;
bool vis[mn];
struct EDGE{int pnt;double dist;EDGE *pre;EDGE (){}EDGE(int _pnt,double _dist,EDGE *_pre):pnt(_pnt),dist(_dist),pre(_pre){}
}Edge[mm],*SPEdge,*edge[mm];inline void addedge(int a,int b,double c){edge[a]new(SP)EDGE(b,c,edge[a]);
}bool SPFA(double ans){memset(cnt,0,sizeof(cnt));for(int i2;in;i) dist[i]DINF;memset(vis,false,sizeof(vis));while(!q.empty()) q.pop();q.push(1);dist[1]0;while(!q.empty()){int iq.front();q.pop();vis[i]false;for(EDGE *jedge[i];j;jj-pre)if(dist[j-pnt]dist[i]ans*j-dist-F[j-pnt]){dist[j-pnt]dist[i]ans*j-dist-F[j-pnt];if(!vis[j-pnt]){vis[j-pnt]true;if(cnt[j-pnt]n) return true;q.push(j-pnt);}}}return false;
}int main(){scanf(%d%d,n,m);for(int i1;in;i) scanf(%lf,F[i]);for(int i1;im;i){scanf(%d%d%lf,x,y,z);addedge(x,y,z);}double low0,highDINF;while(high-loweps){double mid(lowhigh)/2.0;if(SPFA(mid)) lowmid;else highmid;}printf(%.2lf\n,low);return 0;
}转载于:https://www.cnblogs.com/Delostik/archive/2011/07/28/2119329.html
