• 应用
• 登录
• 注册

# P3705 [SDOI2017]新生舞会 题解

## 评论

• 还没有评论

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
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) {
nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
cap[ecnt] = w; cost[ecnt] = x;
nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
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)
Add(s, i, 1, 0), Add(i + n, t, 1, 0);
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;
void add(int x,int y,double fee)
{
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 <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++)
for(register int i=1;i<=n;i++)
for(register int j=1;j<=n;j++)
while(r-l>=0.000000001){
mid=(l+r)/2;
if(judge(mid))l=mid;
else r=mid;
}
printf("%.6lf",l);
}

## 评论

• 还没有评论

(总之是在没有$O_{2}$的情况下疯狂卡常过了这道题)

# $\sum a_{i,j}-\sum Midb_{i,j}=0$

(不就是二分图最大带权匹配吗……会的话不需要我多说吧)

## 卡常数

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=110;typedef double db;db eps=1e-8;int n;
int v[4*N*N];int x[4*N*N];int c[4*N*N];db val[4*N*N];
int al[2*N];int ct=1;int rst[4*N*N];//去掉了所有的结构体，大家凑合着看吧
inline void add(int p,int y)
{
v[++ct]=y;x[ct]=al[p],c[ct]=1;al[p]=ct;rst[ct]=1;
v[++ct]=p;x[ct]=al[y];c[ct]=0;al[y]=ct;rst[ct]=0;
}db cost;db d[2*N];int s;int t;int ctt;int q[4000010];int hd=1;int til;
int fr[2*N];int nu[2*N];bool book[2*N];
inline bool spfa()
{
for(int i=1;i<=ctt;i++){d[i]=-0x3f3f3f3f;}d[s]=0;
for(q[++til]=s;hd<=til;++hd)//这里手写了队列……
{
for(int w=q[hd],i=al[w];i;i=x[i])//spfa不说了
{
if(d[v[i]]<d[w]+val[i]&&c[i]!=0)
{
fr[v[i]]=w;nu[v[i]]=i;d[v[i]]=d[w]+val[i];
if(!book[v[i]]){q[++til]=v[i];book[v[i]]=true;}
}
}book[q[hd]]=false;
}hd=1;til=0;//记得手动清空
if(d[t]==-0x3f3f3f3f){return false;}//这里为了省常数直接+1-1因为边权只有1和0
for(int p=t;p!=s;p=fr[p]){c[nu[p]]-=1;c[nu[p]^1]+=1;}
cost+=d[t];return true;
}db a[N][N];db b[N][N];int tr[N][N];
inline void rebuild(db mid)//这里维护了一个点到边的映射
{
for(int i=1;i<=ct;i++){c[i]=rst[i];}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)//重新设置下边权
{
val[tr[i][j]]=a[i][j]-b[i][j]*mid;
val[tr[i][j]^1]=-val[tr[i][j]];
}
}cost=0;
}
int main()
{
scanf("%d",&n);ctt=2*n;s=++ctt;t=++ctt;
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]);}}
}