gift 分数规划的最大权闭合子图

题目大意：

N个物品,物品间有M组关系,每个物品有一个ai的代价,满足关系后会得到bi的值

求 max(sigma(bi)/sigma(ai))

题解：

很明显的最大权闭合子图，只不过需要处理分数.

这里二分一个答案g

然后直接求sigma(b[i])-sigma(a[i]*g)即可

其中把图中的ai都改成ai*g即可

注意整数处理

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #define RG register
  8 using namespace std;
  9 const int N=4005,M=200005,INF=2e8;
 10 int n,m;double SUM=0,ep=0.0000001;
 11 int gi(){
 12     int str=0;char ch=getchar();
 13     while(ch>'9' || ch<'0')ch=getchar();
 14     while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
 15     return str;
 16 }
 17 int val[N];
 18 struct node{
 19     int x,y,v;
 20 }c[M];
 21 int head[(N+M)],num=1;
 22 struct Lin{
 23     int next,to;double dis;
 24 }a[(N+M)<<2];
 25 void init(int x,int y,double dis){
 26     a[++num].next=head[x];
 27     a[num].to=y;a[num].dis=dis;
 28     head[x]=num;
 29     a[++num].next=head[y];
 30     a[num].to=x;a[num].dis=0;
 31     head[y]=num;
 32 }
 33 int S=0,T,q[N+M],dep[N+M];
 34 bool bfs(){
 35     for(int i=0;i<=T;i++)dep[i]=0;
 36     q[1]=S;dep[S]=1;
 37     int t=0,sum=1,u,x;
 38     while(t!=sum){
 39         t++;x=q[t];
 40         for(RG int i=head[x];i;i=a[i].next){
 41             u=a[i].to;
 42             if(dep[u] || a[i].dis<ep)continue;
 43             dep[u]=dep[x]+1;
 44             q[++sum]=u;
 45         }
 46     }
 47     return dep[T];
 48 }
 49 double dinic(int x,double tot){
 50     if(x==T || !tot)return tot;
 51     int u;double tmp,sum=0;
 52     for(RG int i=head[x];i;i=a[i].next){
 53         u=a[i].to;
 54         if(a[i].dis<ep || dep[u]!=dep[x]+1)continue;
 55         tmp=dinic(u,min(tot,a[i].dis));
 56         a[i].dis-=tmp;a[i^1].dis+=tmp;
 57         sum+=tmp;tot-=tmp;
 58         if(!tot)break;
 59     }
 60     if(sum<ep)dep[x]=0;
 61     return sum;
 62 }
 63 double maxflow(){
 64     double tot=0,tmp;
 65     while(bfs()){
 66         tmp=dinic(S,INF);
 67         while(tmp>=ep)tot+=tmp,tmp=dinic(S,INF);
 68     }
 69     return tot;
 70 }
 71 void Clear(){
 72     num=1;
 73     memset(head,0,sizeof(head));
 74 }
 75 bool check(double g){
 76     Clear();
 77     T=n+m+1;
 78     for(RG int i=1;i<=n;i++)init(S,i,g*(double)val[i]);
 79     for(RG int i=1;i<=m;i++){
 80         init(c[i].x,i+n,INF);
 81         init(c[i].y,i+n,INF);
 82         init(i+n,T,c[i].v);
 83     }
 84     double pap=maxflow();
 85     pap=SUM-pap;
 86     if(pap>=ep)return true;
 87     return false;
 88 }
 89 void work(){
 90     n=gi();m=gi();
 91     for(RG int i=1;i<=n;i++)val[i]=gi();
 92     for(RG int i=1;i<=m;i++)c[i].x=gi(),c[i].y=gi(),c[i].v=gi(),SUM+=c[i].v;
 93     double l=1,r=SUM,mid,ans;
 94     while(l<=r){
 95         mid=(l+r)/2;
 96         if(check(mid)){
 97             ans=mid;
 98             l=mid+ep;
 99         }
100         else r=mid-ep;
101     }
102     printf("%d
",(int)ans);
103 }
104 int main()
105 {
106     freopen("gift.in","r",stdin);
107     freopen("gift.out","w",stdout);
108     work();
109     return 0;
110 }