分数规划

BZOJ 1690

假设求出∑a/∑b>L

L∑b-∑a<0 => ∑(Lb-a)<0即可说明有比L优的解

可以二分L，∑(Lb-a)<0可以通过Dfs_Spfa找负环

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 const int Maxn=2010;
 5 const double eps=1e-3;
 6 struct EDGE
 7 {
 8     int next,to,t;
 9     double w;
10 }edge[Maxn<<3];
11 int head[Maxn],m,n,f[Maxn],u,v,w,cnt;
12 double dis[Maxn];
13 bool flag,vis[Maxn];
14 inline void Add(int u,int v,int t)
15 {edge[cnt].next=head[u];edge[cnt].to=v;edge[cnt].t=t;head[u]=cnt++;}
16 void Build(double p)
17 {
18     for (int i=1;i<=n;i++) 
19         for (int j=head[i];j!=-1;j=edge[j].next)
20             edge[j].w=(double)(edge[j].t)*p-(double)f[edge[j].to];
21 }
22 void Spfa(int u)
23 {
24     vis[u]=true;
25     for (int i=head[u];i!=-1;i=edge[i].next)
26         if (dis[edge[i].to]>dis[u]+edge[i].w)
27         {
28             if (vis[edge[i].to]) {flag=true; return;}
29             dis[edge[i].to]=dis[u]+edge[i].w;
30             Spfa(edge[i].to);
31         }
32     vis[u]=false;
33 }
34 inline bool Check()
35 {
36     memset(vis,false,sizeof(vis));
37     memset(dis,0,sizeof(dis));
38     flag=false;
39     for (int i=1;i<=n;i++)
40     {
41         Spfa(i); if (flag) return true;
42     }
43     return false;
44 }
45 int main()
46 {
47     scanf("%d%d",&n,&m);
48     for (int i=1;i<=n;i++) scanf("%d",&f[i]);
49     memset(head,-1,sizeof(head));
50     for (int i=1;i<=m;i++)
51     {
52         scanf("%d%d%d",&u,&v,&w);
53         Add(u,v,w);
54     }
55     double l=0,r=10000;
56     while (r-l>eps)
57     {
58         double mid=(l+r)/2;
59         Build(mid);
60         if (Check()) l=mid; else r=mid;
61     }
62     printf("%.2lf",l);
63     return 0;
64 }

C++

BZOJ 1486

同理可得

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 const int Maxn=10010;
 5 const double eps=1e-9;
 6 struct EDGE
 7 {
 8     int next,to,t;
 9     double w;
10 }edge[Maxn<<3];
11 int head[Maxn],m,n,u,v,w,cnt;
12 double dis[Maxn];
13 bool flag,vis[Maxn];
14 inline void Add(int u,int v,int t)
15 {edge[cnt].next=head[u];edge[cnt].to=v;edge[cnt].t=t;head[u]=cnt++;}
16 void Build(double p)
17 {
18     for (int i=1;i<=n;i++) 
19         for (int j=head[i];j!=-1;j=edge[j].next)
20             edge[j].w=(double)edge[j].t-p;
21 }
22 void Spfa(int u)
23 {
24     vis[u]=true;
25     for (int i=head[u];i!=-1;i=edge[i].next)
26         if (dis[edge[i].to]>dis[u]+edge[i].w)
27         {
28             if (vis[edge[i].to]) {flag=true; return;}
29             dis[edge[i].to]=dis[u]+edge[i].w;
30             Spfa(edge[i].to);
31         }
32     vis[u]=false;
33 }
34 inline bool Check()
35 {
36     memset(vis,false,sizeof(vis));
37     memset(dis,0,sizeof(dis));
38     flag=false;
39     for (int i=1;i<=n;i++)
40     {
41         Spfa(i); if (flag) return true;
42     }
43     return false;
44 }
45 int main()
46 {
47      
48     scanf("%d%d",&n,&m);
49     memset(head,-1,sizeof(head));
50     for (int i=1;i<=m;i++)
51     {
52         scanf("%d%d%d",&u,&v,&w);
53         Add(u,v,w);
54     }
55     double l=-10000000,r=10000000;
56     while (r-l>eps)
57     {
58         double mid=(l+r)/2;
59         Build(mid);
60         if (Check()) r=mid;else l=mid;
61     }   
62     printf("%.8lf
",l);
63     return 0;
64 }

C++