01分数规划+判负环
看到分数就直接上分数规划嘛……瞎推一下式子就行了。不知道什么是分数规划就去看胡学长论文啦。
一不小心忘记睡觉了。好困啊，把from打成flow差点没看出来……感觉身体被掏空，明天早上还有训练，赶快睡觉，就不写具体的题解了。
滚去睡觉2333
#include<cstdio>
#include<cstring>
#define N 10005
using namespace std;
namespace runzhe2000
{
int n, m, last[N], ecnt, inq[N]; double dis[N];
struct pdge{int from, to, a, b, flow, cost;}pe[N];
struct edge{int next, to; double val;}e[N<<1];
void addedge(int a, int b, double c)
{
e[++ecnt] = (edge){last[a], b, c};
last[a] = ecnt;
}
bool dfs(int x)
{
inq[x] = 1;
for(int i = last[x]; i; i = e[i].next)
{
int y = e[i].to;
if(dis[x] + e[i].val < dis[y])
{
dis[y] = dis[x] + e[i].val;
if(inq[y] || dfs(y)) return 1;
}
}
inq[x] = 0; return 0;
}
bool check(double lim)
{
memset(last,0,sizeof(last)); ecnt=0;
for(int i = 1; i < m; i++)
{
addedge(pe[i].from,pe[i].to,pe[i].b+pe[i].cost+lim);
if(pe[i].flow)addedge(pe[i].to,pe[i].from,pe[i].a-pe[i].cost+lim);
}
for(int i = 1; i <= n; i++) dis[i] = 0, inq[i] = 0;
for(int i = 1; i <= n; i++) if(dfs(i)) return 1;
return 0;
}
void main()
{
scanf("%d%d",&n,&m); n += 2;
for(int i = 1; i <= m; i++)
scanf("%d%d%d%d%d%d",&pe[i].from,&pe[i].to,&pe[i].a,&pe[i].b,&pe[i].flow,&pe[i].cost);
double l = 0, r = 1e9;
for(; r - l > 1e-3; )
{
double mid = (l+r)/2;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.2lf\n",(l+r)/2);
}
}
int main()
{
runzhe2000::main();
}