本文共 1311 字，大约阅读时间需要 4 分钟。
比值最大 分数规划
二分答案之后用费用流进行验证。
据说标称强行乘以1e7换成了整数的二分。
不过貌似实数二分也可以过。
#include #include #include #include #include #include #include using namespace std;#define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i)#define ll long long#define mp make_pair#define eps 1e-7#define inf 1e9#define maxn 50005 int h[maxn],to[maxn],ne[maxn],en=0,fl[maxn],n,S=maxn-2,T=maxn-1;double cost[maxn],a[101][101],b[101][101],dis[maxn];int with[maxn],minn[maxn],inq[maxn]; void add(int a,int b,double c,int d){ to[en]=b;ne[en]=h[a];fl[en]=d;cost[en]=c; h[a]=en++; to[en]=a;ne[en]=h[b];fl[en]=0;cost[en]=-c;h[b]=en++;} queue q; bool SPFA(){ F(i,1,2*n) dis[i]=inf; dis[S]=inf; dis[T]=inf; memset(inq,0,sizeof inq); memset(with,0,sizeof with); memset(minn,0x3f,sizeof minn); q.push(S); inq[S]=1; dis[S]=0; while (!q.empty()) { int x=q.front(); q.pop(); inq[x]=0; for (int i=h[x];i>=0;i=ne[i]) if (dis[to[i]]>dis[x]+cost[i]&&fl[i]>0) { dis[to[i]]=dis[x]+cost[i]; minn[to[i]]=min(minn[x],fl[i]); with[to[i]]=i; if (!inq[to[i]]) q.push(to[i]),inq[to[i]]=1; } } return dis[T] eps) { double mid=(l+r)/2; if (check(mid)) l=mid; else r=mid; } printf("%.6lf\n",(l+r)/2);}
转载于:https://www.cnblogs.com/SfailSth/p/6737591.html