# P3705 [SDOI2017]新生舞会 题解

## 评论

• 还没有评论

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
return bo ? ~res + 1 : res;
}
const int L = 105, N = 5e5 + 5; const double eps = 1e-8;
int n, a[L][L], b[L][L], ecnt, nxt[N], adj[N], go[N], cap[N], len,
que[N], S, T; double cost[N], dis[N], ans;
bool vis[N], walk[N];
void add_edge(int u, int v, int w, double x) {
cap[ecnt] = w; cost[ecnt] = x;
cap[ecnt] = 0; cost[ecnt] = -x;
}
bool spfa() {
int i; for (i = S; i <= T; i++) dis[i] = -1e20, walk[i] = 0;
dis[que[len = 1] = S] = 0;
for (i = 1; i <= len; i++) {
int u = que[i]; vis[u] = 0;
for (int e = adj[u], v; e; e = nxt[e])
if (cap[e] > 0 && dis[u] + cost[e] > dis[v = go[e]]) {
dis[v] = dis[u] + cost[e];
if (!vis[v]) vis[que[++len] = v] = 1;
}
}
return dis[T] >= -1e19;
}
int dfs(int u, int flow) {
if (u == T) return ans += dis[T] * flow, flow;
int res = 0, delta; walk[u] = 1;
for (int e = adj[u], v; e; e = nxt[e])
if (!walk[v = go[e]] && cap[e] > 0 &&
abs(dis[v] - dis[u] - cost[e]) <= eps) {
delta = dfs(v, min(cap[e], flow - res));
if (delta) {
cap[e] -= delta; cap[e ^ 1] += delta;
res += delta; if (res == flow) break;
}
}
return res;
}
double mcmf() {
ans = 0;
while (spfa()) dfs(S, 0x3f3f3f3f);
return ans;
}
bool check(double mid) {
int i, j; ecnt = S = 1; T = (n << 1) + 2;
for (i = S; i <= T; i++) adj[i] = 0;
for (i = 1; i <= n; i++) add_edge(S, i + 1, 1, 0);
for (i = n + 2; i < T; i++) add_edge(i, T, 1, 0);
for (i = 1; i <= n; i++) for (j = 1; j <= n; j++)
add_edge(i + 1, j + n + 1, 1, 1.0 * a[i][j] - 1.0 * b[i][j] * mid);
double ap = mcmf(); return abs(ap) <= eps || ap > eps;
}
int main() {
int i, j; n = read();
for (i = 1; i <= n; i++) for (j = 1; j <= n; j++)
for (i = 1; i <= n; i++) for (j = 1; j <= n; j++)
double l = -1e7, r = 1e7;
while (abs(r - l) > eps) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.6lf\n", r);
return 0;
}

## 评论

• 还没有评论

C = (a1 + a2 + …… + an) / (b1 + b2 + …… + bn)
(b1 + b2 + …… + bn) * C = (a1 + a2 + …… + an)
(a1 + a2 + …… + an) - (b1 + b2 + …… + bn) * C = 0
(a1 - b1 * C) + (a2 - b2 * C) + …… + (an - bn * C) = 0

1)将源点向每个男生连一条流量为1、费用为0的边

2)将每个女生向汇点连一条流量为1、费用为0的边

3)将每一对男女舞伴间连一条流量为1、费用为[a[i][j] - b[i][j] * C]的边

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const double Maxn = 1e9;
const int N = 205, M = 8e4 + 5;
const double eps = 1e-8;
int pre[N], nxt[M], to[M], lst[N], fr[M], flw[M], Q[M];
int n, s, t, T; bool vis[N];
double a[N][N], b[N][N], cst[M], Ans, dis[N];
template <class T> inline void CkMin(T &a, const T b) {if (a > b) a = b;}
inline void Add(const int x, const int y, const int z, const double g)
{
nxt[++T] = lst[x]; lst[x] = T; to[T] = y; fr[T] = x; flw[T] = z; cst[T] = g;
nxt[++T] = lst[y]; lst[y] = T; to[T] = x; fr[T] = y; flw[T] = 0; cst[T] = -g;
}
inline bool Bul()
{
for (int i = s; i <= t; ++i) dis[i] = -Maxn;
int te = 0, we = 1, x, y;
dis[Q[1] = s] = 0.0;
while (te < we)
{
x = Q[++te]; vis[x] = false;
for (int i = lst[x]; i; i = nxt[i])
if (dis[y = to[i]] < dis[x] + cst[i] && flw[i])
{
dis[y] = dis[x] + cst[i]; pre[y] = i;
if (!vis[y]) vis[y] = true, Q[++we] = y;
}
}
return dis[t] > -Maxn;
}
inline void Deal()
{
int Mif = Maxn;
for (int i = pre[t]; i; i = pre[fr[i]]) CkMin(Mif, flw[i]);
for (int i = pre[t]; i; i = pre[fr[i]])
flw[i] -= Mif, flw[i ^ 1] += Mif, Ans += (double)Mif * cst[i];
}
inline bool check(const double mi)
{
T = 1; memset(lst, 0, sizeof(lst));
for (int i = 1; i <= n; ++i)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
Add(i, j + n, 1, a[i][j] - mi * b[i][j]);
Ans = 0.0; while (Bul()) Deal();
return (Ans <= 0);
}
int main()
{
scanf("%d", &n); s = 0; t = (n << 1) + 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) scanf("%lf", &a[i][j]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) scanf("%lf", &b[i][j]);
double l = 0, r = 1e4;
while (r - l >= eps)
{
double mid = (l + r) / 2;
(check(mid) ? r : l) = mid;
}
return printf("%.6lf\n", l), 0;
}

## 评论

• 还没有评论

### 分数规划，最大费用最大流

$sigma\ a_{i,j}/sigma\ b_{i,j}=C$

$sigma\ a_{i,j}=sigma\ b_{i,j}*C$

$sigma\ a_{i,j}-sigma\ b_{i,j}*C=0$

$sigma(\ a_{i,j}-b_{i,j}*C)=0$

C就是我们要求的最大值，我们可以$mid$实数二分它，对于每一个$mid$，求出这种情况下$sigma(\ a_{i,j}-b_{i,j}*mid)=0$的最大值，如果最大值小于0，就说明$mid>C$，反之亦然。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#define inf 0x7fffffff
using namespace std;
{
int ans=0,fh=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
fh=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
return ans*fh;
}
const int maxn=300;
const int maxm=10010;
const double eps=0.00000001;
double f[maxm*2],bj[maxn],l,r,mid;
bool cz[maxn];
queue<int>q;
{
u[++num]=x;
v[num]=y;
w[num]=1;
f[num]=fee;
u[++num]=y;
v[num]=x;
w[num]=0;
f[num]=-fee;
}
bool spfa()
{
memset(qq,0,sizeof(qq));
for(int i=1;i<=n*2+2;i++)
bj[i]=2100000000;
memset(ll,0,sizeof(ll));
q.push(s);
bj[s]=0;
ll[s]=inf;
while(!q.empty())
{
int now=q.front();
q.pop();
cz[now]=0;
if(w[i]&&bj[v[i]]>bj[now]+f[i])
{
bj[v[i]]=bj[now]+f[i];
ll[v[i]]=min(w[i],ll[now]);
qq[v[i]]=i;
if(!cz[v[i]])
q.push(v[i]),cz[v[i]]=1;
}
}
return qq[t]>0;
}
double EK()
{
double fee=0;
while(spfa())
{
int liu=ll[t];
for(int i=qq[t];i;i=qq[u[i]])
w[i]-=liu,w[i^1]+=liu;
fee+=liu*bj[t];
}
return fee*-1;
}//最大费用最大流
double work(double x)
{
num=1;
for(int i=1;i<=n;i++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
return EK();
}
int main()
{
s=n*2+1;t=s+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
r=1000000;
while(r-l>eps)
{
mid=(l+r)*0.5;
double dd=work(mid);
if(dd>=0)
l=mid;
else
r=mid;
}//实数二分
printf("%.6lf",l);
fclose(stdin);
return 0;
}

## 评论

• 还没有评论

#include<bits/stdc++.h>
#define MAXN 1005
#define inf 1010580540
#define eps 1e-8
using namespace std;
deque <int> q;
int cnt,fst[MAXN],nxt[MAXN<<5],to[MAXN<<5],w[MAXN<<5],cur[MAXN];
int n,m,S,T,maxflow;
double dis[MAXN],a[MAXN][MAXN],b[MAXN][MAXN],cot[MAXN<<5],mincost;
bool inq[MAXN],vis[MAXN];
void AddEdge(int u,int v,int c,double fl)
{
to[++cnt]=v;
nxt[cnt]=fst[u];
fst[u]=cnt;
w[cnt]=c;
cot[cnt]=fl;
}
bool Spfa()
{
for(int i=S;i<=T;i++) dis[i]=inf;
memset(inq,0,sizeof(inq));
q.push_front(T);
dis[T]=0;
inq[T]=1;
while(!q.empty())
{
int u=q.front();
q.pop_front();
inq[u]=0;
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(dis[v]>dis[u]-cot[i] && w[i^1])
{
dis[v]=dis[u]-cot[i];
if(!inq[v])
{
if(!q.empty() && dis[v]<dis[q.front()]) q.push_front(v);
else q.push_back(v);
inq[v]=1;
}
}
}
}
return dis[S]!=inf;
}
int Dfs(int u,int flow)
{
vis[u]=1;
if(u==T || !flow) return flow;
int used=0;
for(int &i=cur[u];i;i=nxt[i])
{
int v=to[i];
if(dis[v]==dis[u]-cot[i] && w[i] && !vis[v])
{
int fl=Dfs(v,min(flow,w[i]));
if(fl)
{
used+=fl;
flow-=fl;
w[i]-=fl;
w[i^1]+=fl;
if(!flow) break;
}
}
}
return used;
}
void zkwMCMF()
{
while(Spfa())
{
vis[T]=1;
while(vis[T])
{
memset(vis,0,sizeof(vis));
memcpy(cur,fst,sizeof(fst));
int fl=Dfs(S,inf);
maxflow+=fl;
mincost+=dis[S]*fl;
}
}
mincost=-mincost;
}
bool Check(double mid)
{
maxflow=mincost=0;
cnt=1;
memset(fst,0,sizeof(fst));
for(int i=1;i<=n;i++)
{
}
for(int i=n+1;i<=n*2;i++)
{
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
}
}
zkwMCMF();
return fabs(mincost)<=eps || mincost>eps;
}
int main()
{
scanf("%d",&n);
S=0;
T=n*2+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) scanf("%lf",&a[i][j]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) scanf("%lf",&b[i][j]);
}
double l=0,r=1e4;
while(r-l>eps)
{
double mid=(l+r)/2.0;
if(Check(mid)) l=mid;
else r=mid;
}
printf("%.6lf\n",r);
return 0;
}

## 评论

• 还没有评论

#include <cstdio>
#include <cstring>
#define min(X,Y) ((X)<(Y)?(X):(Y))

int vt[180001],flow[301],q[100001],h,t,S,T,pre[301];
bool inq[301];
void push(int s,int t,int val,double c){
b[k]=t;
v[k]=val;
cost[k]=c;
}
void link(int s,int t,int val,double c){
push(s,t,val,c);
push(t,s,0,-c);
}
bool spfa(){
for(int i=S;i<=T;i++)dis[i]=1000000000.0;
h=t=0;
q[++t]=S;
inq[S]=1;
dis[S]=0.0;
flow[S]=0x7f7f7f7f;
while(h<t){
++h;inq[q[h]]=0;
if(dis[b[i]]>dis[q[h]]+cost[i]&&v[i]){
dis[b[i]]=dis[q[h]]+cost[i];
flow[b[i]]=min(flow[q[h]],v[i]);
pre[b[i]]=i;
if(!inq[b[i]])inq[b[i]]=1,q[++t]=b[i];
}
}
return dis[T]!=1000000000.0;
}
bool judge(double u){
double ans=0.0;
k=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
}
while(spfa()){
int tem=T;
while(tem!=S){
v[pre[tem]]-=flow[T];
v[pre[tem]^1]+=flow[T];
tem=b[pre[tem]^1];
}
ans+=(double)flow[T]*dis[T];
}
return ans<0.0;
}
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int main(){
T=n+n+1;
for(register int i=1;i<=n;i++)
for(register int j=1;j<=n;j++)