题解：P6129 [JSOI2012] 铁拳

· · 题解

[JSOI2012] 铁拳

日志

2025.6.11 申请题解成功

2025.6.12 修复边权负数及其他细节描述

鸣谢

感谢 xzf_200906 提供的解题思路及指导！

题意

给出 n 场比赛（题目中表示为 m）及 m 个人（题目中表示为 n），每个人会给一场比赛提供正价值和另一场比赛负价值，且价值为一个浮动区间，现给出每场比赛对比上一场比赛的价值之差，请判断无方案满足题意或缩小每人的浮动区间，以两位小数形式输出。

思路

我们看到样例可以大胆猜想：

答案一定为整数区间。

仔细想想不难证明，因为初始范围和价值都为整数，最后范围是不可能出现分数的。假设存在那么必然可以进一步缩小。

接着我们可以通过区间来想到一些算法，不过在我们的简化题意中提到会给比赛改变权值且为区间，这给了我们一个思考方向：图。

朝着这个思路想下去，或许能想到一种冷门算法：

有上下界网络流

此算法正好可以给每条边赋区间流量，与我们的思路吻合。

再看数据范围：

N,M(N\le200,M\le100)

时间非常充足，或许可以一试。

细节处理及实现

建图

对于一场比赛建一个点，那么有一个第 u 场进来的第 v 场出去的人贡献为 [l,r]。此时我们由 u 向 v 连边，上下界为 l,r。 但此时有两个问题，我们有从第 0 场进来和第 m+1 场出去的人，以及我们需要对于每条边求答案，不能全部建边啊。

对于第一个问题，从一个虚拟点 s 向第 0 场进来的人连边即可，上下界为 l,r。此时等价于直接给第 v 场加上负权值。

同理，从第 m+1 场出去的人向一个虚拟点 t 连边即可，上下界为 l,r。此时等价于直接给第 u 场加上正权值，对于既从第 0 场进来也第 m+1 场出去的人则可不加，但也可直接连边虚拟点 s 和虚拟点 t。

    cin>>m;
    rep(i,1,m){
        cin>>c[i].w1>>c[i].w2>>c[i].u>>c[i].v;
        if(c[i].u==0) c[i].u=n+1;
        if(c[i].v==0) c[i].v=n+2;
    }

为了使对于答案不影响，虚拟点直接应该要有一条上下界为 0,INF 的边连接 t 和 s。

对于第二个问题，我们可以对于我们枚举的求答案的边更改建边方式：让一个虚拟点 S 向 v 连边， u 向一个虚拟点 T 连边，最后为不影响答案建一条上下界为 0,INF 的边连接 T 和 S，这样最后答案就会存在连接 T 和 S 的反边上。

然后对于一场比赛 i 比上次增加 x 价值，那么

当 x 为正数

则虚拟点 s 向 i 连边，上下界为 x,x。

当 x 为负数

则 i 向虚拟点 t 连边，上下界为 -x,-x。

这样即可强制给 i 流入或流出一定流量，且由于上文连边虚拟点 s 和虚拟点 t则对答案无影响。

        a[++ss]={n+2,n+1,0,INF};//a用于存储将建的边，格式为以u连向v一条上下界为[l,r]的边。建边t到s
        rep(i,1,n){
            if(b[i]>0) a[++ss]={n+1,i,b[i],b[i]};//x为正
            if(b[i]<0) a[++ss]={i,n+2,-b[i],-b[i]};//x为负
        }
        rep(i,1,m){
            if(i!=id) a[++ss]={c[i].u,c[i].v,c[i].w1,c[i].w2};
            else{//枚举答案的边
                a[++ss]={S2,c[i].v,c[i].w1,c[i].w2};
                a[++ss]={c[i].u,T2,c[i].w1,c[i].w2};
            }
        }
        rep(i,1,ss){//模板部分
            long long u=a[i].u,v=a[i].v,w1=a[i].w1,w2=a[i].w2,w;
            w=w2-w1;
            put(u,v,w);
            put(v,u,0);
            d2[u]+=w1;
            d[v]+=w1;
        }
        t2=t;
        rep(i,1,n+6){
            nowww[i]=now[i];
        }//记录当前边，后面回溯，模板部分
        put(T2,S2,1e18);//建边T到S
        put(S2,T2,0);

计算答案及判断输入正误

建完边就很简单了，对于输入正误跑一边可行流即可。

对于答案右边界（最大流）就要根据可行流流量加上 S 向 T 的最大流量，答案左边界（最小流）就要根据答案右边界（当前流）减去 T 向 S 的最大流量。具体原因此处不作解释，可去学习模板有源汇有上下界最大流/最小流。

        long long ans1=0,ans2=0;//答案
        ans=0;//dinic结果变量
        dinic();
        if(ans!=sss){//可行流模板
            cout<<"-1\n";
            return 0;
        }
        t=t2;//拆去不需要的边，回溯，最值流模板
        rep(i,1,n+5){
            now[i]=nowww[i];
        }
        ans2=val[t2+2];//当前流
        ans=0;
        S=S2,T=T2;//超级原点、汇点,也是前面S、T叫做S2、T2的原因
        dinic();
        ans2+=ans;//最大流
        ans1=ans2;//当前流
        ans=0;
        S=T2,T=S2;//反着跑最小流
        dinic();
        ans1-=ans;//最小流
        cout<<ans1<<".00 "<<ans2<<".00\n";//愉快的输出~

代码

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=2e4+7,M=4e5+7,INF=1e18;
long long n,m,S2,T2,b[N],d[N],d2[N],S,T,t=1,t2,p[M],now[N],son[M],val[M],noww[N],nowww[N],h[N],ans;
struct node{
    long long u,v,w1,w2;
};
node a[M],c[M];
void put(int a,int b,long long c){
    p[++t]=now[a];
    now[a]=t;
    son[t]=b;
    val[t]=c;
}
bool bfs(){
    rep(i,1,n+6){
        noww[i]=now[i];
        h[i]=0;
    }
    h[S]=1;
    queue<int> q;
    q.push(S);
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=noww[u];i;i=p[i]){
            int y=son[i];
            if(val[i]&&h[y]==0){
                h[y]=h[u]+1;
                q.push(y);
                if(y==T) return 1;
            }
        }
    }
    return 0;
}
long long dfs(int x,long long s){
    if(x==T) return s;
    long long sum=0;
    for(long long &i=noww[x];i;i=p[i]){
        int y=son[i];
        if(val[i]&&h[y]==h[x]+1){
            long long ss=dfs(y,min(s,val[i]));
            val[i]-=ss;
            val[i^1]+=ss;
            s-=ss;
            sum+=ss;
            if(s==0) break;
        }
    }
    if(sum==0) h[x]=0;
    return sum;
}
void dinic(){
    while(bfs()){
        ans+=dfs(S,1e18);
    }
}
int main(){
    cin>>n;
    b[0]=1e18;
    rep(i,1,n){
        cin>>b[i];
    }
    cin>>m;
    rep(i,1,m){
        cin>>c[i].w1>>c[i].w2>>c[i].u>>c[i].v;
        if(c[i].u==0) c[i].u=n+1;
        if(c[i].v==0) c[i].v=n+2;
    }
    rep(id,1,m){
        rep(i,1,n+6){
            now[i]=d[i]=d2[i]=0;
        }
        t=1;
        S=n+1+4,T=n+1+5;
        S2=n+1+2,T2=n+1+3;
        long long ss=0,sss=0,sss2=0;
        a[++ss]={n+2,n+1,0,INF};
        rep(i,1,n){
            if(b[i]>0) a[++ss]={n+1,i,b[i],b[i]};
            if(b[i]<0) a[++ss]={i,n+2,-b[i],-b[i]};
        }
        rep(i,1,m){
            if(i!=id) a[++ss]={c[i].u,c[i].v,c[i].w1,c[i].w2};
            else{
                a[++ss]={S2,c[i].v,c[i].w1,c[i].w2};
                a[++ss]={c[i].u,T2,c[i].w1,c[i].w2};
            }
        }
        rep(i,1,ss){
            long long u=a[i].u,v=a[i].v,w1=a[i].w1,w2=a[i].w2,w;
            w=w2-w1;
            put(u,v,w);
            put(v,u,0);
            d2[u]+=w1;
            d[v]+=w1;
        }
        t2=t;
        rep(i,1,n+6){
            nowww[i]=now[i];
        }
        put(T2,S2,1e18);
        put(S2,T2,0);
        rep(i,1,n+4){
            if(d[i]>d2[i]){
                sss+=d[i]-d2[i];
                put(S,i,d[i]-d2[i]);
                put(i,S,0);
            }
            else if(d[i]<d2[i]){
                sss2+=d2[i]-d[i];
                put(i,T,d2[i]-d[i]);
                put(T,i,0);
            }
        }
        if(sss!=sss2){
            cout<<"-1\n";
            return 0;
        }
        long long ans1=0,ans2=0;
        ans=0;
        dinic();
        if(ans!=sss){
            cout<<"-1\n";
            return 0;
        }
        t=t2;
        rep(i,1,n+5){
            now[i]=nowww[i];
        }
        ans2=val[t2+2];
        ans=0;
        S=S2,T=T2;
        dinic();
        ans2+=ans;
        ans1=ans2;
        ans=0;
        S=T2,T=S2;
        dinic();
        ans1-=ans;
        cout<<ans1<<".00 "<<ans2<<".00\n";
    }
    return 0;
}