题解 BZOJ 1313 取整矩阵

题目


题里的矩阵是这样的:

A11 A12 A13… A1n-1 B1
A21 ………. A2n-1 B2
……
An-11 An-12….An-1n-1 Bn-1
C1 C2 C3… Cn-1 0

需要取整。每个元素大概有两种选择,一种是floor另一种是ceil。

这两种之间差了1。

网络流。

S 向所有的B连边 下界 floor(Bi) 上界 ceil(Bi)。

Bi向Cj连 下界 floor(Aij) 上界 ceil (Aij)的边。

Cj向T连边,差不多。

有上下界的S-T最大流即可。

我写的二分。

注意整数和负数。

ps.(int)强制转换是向0 取整啊。。

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
int H[105*3],X[10005*4],P[10005*4],tot=1,flow[10005*4];
int floww[10005*4];
int in[105*3];
void add(int x,int y,int z){
    P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;
}
int d[105*3];
int S,T,SS,TT;
queue<int> q;
const double eps(1e-8);
bool bfs(){
    memset(d,0,sizeof d);
    d[SS]=1;
    q.push(SS);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=H[x];i;i=X[i]){
            if(!d[P[i]]&&flow[i]>0){
                d[P[i]]=d[x]+1;
                q.push(P[i]);
            }
        }
    }
    return d[TT];
}
int hs,ht;
int dfs(int x,int a){
    if(x==TT||a==0) return a;
    int tmp,f=a;
    for(int i=H[x];i;i=X[i]){
        if(d[P[i]]==d[x]+1&&flow[i]>0){
            tmp=dfs(P[i],min(flow[i],a));
            a-=tmp;
            flow[i]-=tmp;
            flow[i^1]+=tmp;
            if(!a) break;
        }
    }
    if(f==a) d[x]=-1;
    return f-a;
}
double Matrix[105][105];
int n,tott;
int Sum;
int Dinic(){
    int ff=0;
    while(bfs()){
        ff+=dfs(SS,2000000000);
    }
    return ff;
}

bool judge(int lim){
    in[T]-=lim;
    in[S]+=lim;
    int tmp=Sum;
    if(in[S]>0)add(SS,S,in[S]),add(S,SS,0),tmp+=in[S];
    else add(S,TT,-in[S]),add(TT,S,0);
    if(in[T]>0)add(SS,T,in[T]),add(T,SS,0),tmp+=in[T];
    else add(T,TT,-in[T]),add(TT,T,0);
    in[T]+=lim;
    in[S]-=lim;
    if(Dinic()==tmp){
        return 1;
    }else return 0;
}

int main(){
    S=300,T=301;
    SS=298,TT=299;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%lf",&Matrix[i][j]);
        }
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<n;j++){
            Matrix[i][j]+=1000;
        }
        Matrix[i][n]+=1000*(n-1);
        Matrix[n][i]+=1000*(n-1);
    }

    add(T,S,200000500);
    add(S,T,0);
    for(int i=1;i<n;i++){
        in[S]-=floor(Matrix[i][n]-eps);
        in[i<<1]+=floor(Matrix[i][n]-eps);
        add(S,i<<1,1);add(i<<1,S,0);
        in[T]+=floor(Matrix[n][i]-eps);
        in[i<<1|1]-=floor(Matrix[n][i]-eps);
        add(i<<1|1,T,1);add(T,i<<1|1,0);
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<n;j++){
            in[i<<1]-=floor(Matrix[i][j]-eps);
            in[j<<1|1]+=floor(Matrix[i][j]-eps);
            add(i<<1,j<<1|1,1);
            add(j<<1|1,i<<1,0);
        }
    }
    for(int i=1;i<n;i++){
        if(in[i<<1]>0) add(SS,i<<1,in[i<<1]),add(i<<1,SS,0),Sum+=in[i<<1];
        else add(i<<1,TT,-in[i<<1]),add(TT,i<<1,0);
        if(in[i<<1|1]>0) add(SS,i<<1|1,in[i<<1|1]),add(i<<1|1,SS,0),Sum+=in[i<<1|1];
        else add(i<<1|1,TT,-in[i<<1|1]),add(TT,i<<1|1,0);
    }
    hs=H[S],ht=H[T];
    int hss,htt;
    hss=H[SS],htt=H[TT];
    memcpy(floww,flow,sizeof flow);
    tott=tot;
    int l=0,r=200000100;
    while(r-l>1){
        int mid=(l+r)>>1;
        memcpy(flow,floww,sizeof flow);
        tot=tott;
        H[S]=hs;H[T]=ht;H[SS]=hss;H[TT]=htt;
        if(judge(mid)){
            l=mid;
        }else{
            r=mid;
        }
    }
    printf("%d\n",(l-1000*(n-1)*(n-1))*3);
    return 0;
}
评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框