[SDOI2017]新生舞会 0/1分数规划

～～～题面～～～

题解：

0/1分数规划，，，但是竟然有诡异的精度问题？？？因为这个被卡了好久

中途还写过一次KM，，，结果陷入死循环，，，我大概是写了一个假KM，，，于是放弃KM，回来调费用流

这个题面也很直白啊～～～

我们令C>=x,

然后二分求出最大的x即可，

每次跑费用流前重新定义边权

a[i] - mid * b[i]

然后跑最大费用最大流看看跑出来能不能有大于0的费用就可以了

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define R register int
  4 #define AC 410
  5 #define ac 40000
  6 #define eps 1e-7
  7 #define inf -9000000000LL
  8 #define getchar() *o++
  9 #define D printf("line in %d
",__LINE__);
 10 char READ[5000100],*o=READ;
 11 int n,s,t;
 12 double maxn,mid,ans;
 13 int tmp[AC][AC],last[AC];
 14 int Head[AC],Next[ac],date[ac],haveflow[ac],disflow[AC],tot=1;
 15 double dis[ac],cost[ac],a[ac],b[ac];
 16 bool z[AC];
 17 deque <int> q;
 18 /*01分数规划，二分x，然后跑最大费用最大流，看费用是否大于等于0，大于等于0即合法。
 19 1 ~ n 为女生，n+1 ~ 2*n 为男生 ，s = 2*n+1 ,t = 2*n+2*/
 20 
 21 inline int read()
 22 {
 23     int x=0;char c=getchar();
 24     while(c > '9' || c < '0') c=getchar();
 25     while(c >= '0' && c <='9') x=x*10+c-'0',c=getchar();
 26     return x;
 27 }
 28 
 29 inline void add(int f,int w,int aa,int bb)
 30 {
 31     date[++tot]=w,Next[tot]=Head[f],Head[f]=tot,a[tot]=aa,b[tot]=bb;
 32     date[++tot]=f,Next[tot]=Head[w],Head[w]=tot;    
 33 }
 34 
 35 inline void upmax(double &a,double b)
 36 {
 37     if(b > a) a = b;
 38 }
 39 
 40 void pre()
 41 {
 42     int a;
 43     n=read();
 44     s=2 * n + 1,t=2 * n + 2;
 45     for(R i=1;i<=n;i++)
 46         for(R j=1;j<=n;j++)
 47             tmp[i][j]=read();
 48     for(R i=1;i<=n;i++)
 49         for(R j=1;j<=n;j++)
 50         {
 51             a=read();
 52             add(i,n + j,tmp[i][j],a);
 53             upmax(maxn,(double)tmp[i][j] / (double)a);
 54         }
 55     for(R i=1;i<=n;i++) add(s,i,0,0);
 56     for(R i=n+1;i<=2*n;i++) add(i,t,0,0);    
 57 }
 58 
 59 void aru()
 60 {
 61     int x=t;
 62     while(x != s)
 63     {
 64         haveflow[last[x]] -= disflow[x];//是减掉disflow[x]啊
 65         haveflow[last[x] ^ 1] += disflow[x];
 66         x=date[last[x] ^ 1];
 67     }
 68     ans += disflow[t] * dis[t];
 69 
 70 }
 71 
 72 bool spfa()
 73 {
 74     int x,now;
 75     z[s]=true,dis[s]=0,disflow[s]=INT_MAX;
 76     q.push_front(s);
 77     while(!q.empty())
 78     {
 79         x=q.front();
 80         q.pop_front();
 81         z[x]=false;
 82         for(R i=Head[x]; i ;i=Next[i])
 83         {
 84             now=date[i];
 85             if(haveflow[i] && dis[now] < dis[x] + cost[i])
 86             {
 87                 dis[now] = dis[x] + cost[i];
 88                 disflow[now] = min(haveflow[i],disflow[x]);//是用当前边！的haveflow和当前点！的disflow的比较
 89                 last[now] = i;
 90                 if(!z[now] && now != t)//t当然不能进来了 
 91                 {
 92                     if(!q.empty() && dis[now] > dis[q.front()])    q.push_front(now);
 93                     else q.push_back(now);
 94                     z[now]=true;
 95                 }
 96             }
 97         }
 98     }
 99     x=t;
100     if(dis[t] != inf) aru();
101     return dis[t] != inf;
102 }
103 
104 bool check()
105 {
106     int bb=n * 2 + 2;
107     for(R i=1;i<=bb;i++) dis[i]=inf;//要手动inf,,error!!!怎么可以改了下面不改这里，，，
108     ans=0;
109     for(R i=2;i<=tot;i+=2)//枚举正向边
110     {
111         haveflow[i] = 1;//所有边默认流量都为1
112         haveflow[i+1] = 0;//反向边当然是0
113         cost[i] = a[i] - mid * b[i];
114         cost[i+1] = -cost[i];//重新建图 
115     }
116     while(spfa()) //貌似因为是double,所以memset 128不好用了
117         for(R i=1;i<=bb;i++) dis[i] = inf;
118     return ans >= 0;
119 }
120 
121 void half()
122 {
123     double l=0,r=10000;
124     while(r - l > eps)
125     {
126         mid = (l + r) / 2;//因为是实数，所以没有什么偏向问题
127         if(check()) l = mid;
128         else r = mid;//error!!!!!!!!所以说是因为-eps才错的？
129     }//啊啊啊啊啊啊啊啊啊啊那为什么不能减啊!!!!!!!!
130     printf("%.6lf
",l);
131 }
132 
133 int main()
134 {
135 //    freopen("in.in","r",stdin);
136     fread(READ,1,5000000,stdin);
137     pre();
138     half();
139 //    fclose(stdin);
140     return 0;
141 }