P6054 开门大吉

· · 题解

\text{Foreword}

upd：图挂了，但懒得修，想看图可以去 [CSDN]看(https://blog.csdn.net/BUG_Creater_jie/article/details/122745566)

本题的大部分题解采用了一个连反向不限流边的做法，但这似乎并没有抓到问题的实质，而是对问题的一个间接的修正。
本文配合图像对这个问题进行了重点讨论，希望管理员能给予通过。

\text{Description}

P6054 开门大吉

若一位选手答对第 $i$ 题，会在已得到奖励的基础上，再得到 $c_i$ 元奖励。选手总是从第一道开始，按顺序答题的。 同时，为了防止过多的选手做同一套题，还有 $y$ 条形如“第 $i$ 位选手的套题编号必须至少比第 $j$ 位的大 $k$”的限制。 你需要给每一位选手分配一套题（不同选手可以相同），使得所有人的期望奖励和最小。

\text{Solution}

安利一下我的网络流博客。

首先，我们可以简单的算出 i 选手选套题 j 的期望价值 v_{i,j}。
关键就在于如何表示限制。
建出 n 条长度为 m+1 的链，设链上的点为 p_{1...n,1..m+1}，连边 (S,p_{i,1},INF),(p_{i,m+1},T,INF),(p_{i,j},p_{i,j+1},v_{i,j})。断掉 (p_{i,j},p_{i,j+1},v_{i,j}) 的边即表示令 i 选手做 j 号题。
这样建图之后限制就容易表示了，设 i 选手比 j 选手题目编号至少大 k，就对于所有合法的下标 x，均连边 (p_{j,x},p_{i,x+k},INF) 即可。

但是这样是无法通过本题的。
主流题解都说还需要加上 (p_{i,j+1},p_{i,j},INF) 的边，以实现限制的传递性（或者说保证每条链只断一条边），但我认为这并不是问题的本质，这个连边方法并不是必须的，实践结果也证明了这一点。
我们来看看原来的做法到底为什么出错。
原来的连边方式其实是很健全的，它本身已经有了传递性，如： 红线和绿线限制已经可以进行传递，形成黄色的限制。
那么为什么我们难以通过一些测试点呢？
因为我们的限制没有加全！
题解和我一开始的写法对于限制的加边一般都是写成类似下边的形式：

for(int j=max(1,1-k);j<=m+1&&j+k<=m+1;j++) add(id[y][j],id[x][j+k],inf);

但正确的写法应该是：

for(int j=max(1,1-k);j<=m+1;j++) add(id[y][j],id[x][min(j+k,m+1)],inf);

这两个具象一下就是两张图的差别：（图片可见文首链接）

注意到，在第一种加法中，后面的两个点没有被限制，成了“法外之地”，这也是为什么加完反向边可以把这个问题修正的原因。而在新的加边方式上，那两个点直接和点 m+1 相连，由于点 m+1 和 T 连有 INF 的边，这本质也就表明这两个点必然不能被选取，是符合事实的。

即使可以通过加反向边的方式通过本题，从问题的本质来看也是不太优美的。因此，建议直接把加限制边的方式修改，而不是进行侧面的修正。

\text{Code}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
    ll x(0),f(1);char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
const int N=2e5+100;
const int M=2e6+100;
const double inf=1e11;
const double eps=1e-6;

int n,m,num,y;
int flag;

int tot,s,t;
struct node{
    int to,nxt;
    double cap;
}p[M<<1];
int fi[N],cur[N],cnt;
inline void addline(int x,int y,double c){
    p[++cnt]=(node){y,fi[x],c};fi[x]=cnt;
}
inline void add(int x,int y,double c){
    //printf("%d->%d cap=%.2lf\n\n",x,y,c);
    addline(x,y,c);addline(y,x,0);
}
int bel[N];
queue<int>que;
int bfs(){
    fill(bel,bel+1+tot,0);
    bel[s]=1;que.push(s);
    while(!que.empty()){
        int now=que.front();que.pop();
        for(int i=cur[now]=fi[now];~i;i=p[i].nxt){
            int to=p[i].to;
            if(p[i].cap<eps||bel[to]) continue;
            bel[to]=bel[now]+1;
            que.push(to);
        }
    }
    return bel[t];
}
double dfs(int x,double lim){
    if(x==t||lim<eps) return lim;
    double res(0);
    for(int &i=cur[x];~i;i=p[i].nxt){
        int to=p[i].to;
        if(bel[to]!=bel[x]+1) continue;
        double add=dfs(to,min(lim,p[i].cap));
        res+=add;lim-=add;
        p[i].cap-=add;p[i^1].cap+=add;
        //printf("x=%d to=%d add=%lf\n",x,to,add);
        if(lim<eps) break;
    }
    if(res<eps) bel[x]=-1;
    return res;
}
void dinic(){
    double flow(0),tmp(0);
    while(bfs()){
        while((tmp=dfs(s,inf))>eps) flow+=tmp;
        if(flow>=inf){
            puts("-1");return;
        }
    }
    printf("%lf\n",flow);
    return;
}
int id[90][90];
int c[90];
double ans;
double f[90][90][90],pp[90][90][90],val[90][90];
void init(){
    ans=0;
    tot=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m+1;j++) id[i][j]=++tot;
    }
    s=++tot;t=++tot;
    memset(fi,-1,sizeof(fi));cnt=-1;
}
void calc(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            pp[i][j][0]=1;val[i][j]=0;
            for(int k=1;k<=num;k++) pp[i][j][k]=pp[i][j][k-1]*f[i][j][k];
            for(int k=1;k<=num;k++){
                pp[i][j][k]=pp[i][j][k]*(1-f[i][j][k+1]);
                val[i][j]+=pp[i][j][k]*c[k];
            }
            //printf("i=%d j=%d val=%lf\n",i,j,val[i][j]);
        }
    }
}

void work(){
    n=read();m=read();num=read();y=read();
    init();
    for(int i=1;i<=num;i++) c[i]=read()+c[i-1];
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            for(int k=1;k<=num;k++) scanf("%lf",&f[i][j][k]);
        }
    }
    calc();
    for(int i=1;i<=n;i++){
        add(s,id[i][1],inf);
        add(id[i][m+1],t,inf);
        for(int j=1;j<=m;j++){
            add(id[i][j],id[i][j+1],val[i][j]);//add(id[i][j+1],id[i][j],inf);
        }
    }
    for(int i=1;i<=y;i++){
        int x=read(),y=read(),k=read();
        for(int j=max(1,1-k);j<=m+1;j++) add(id[y][j],id[x][min(j+k,m+1)],inf);
    }
    dinic();

    return;
}
signed main(){
    #ifndef ONLINE_JUDGE
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    #endif
    int T=read();
    while(T--) work();
    return 0;
}
/*
1
3 2 4 1
10 10 10 20
0.3 0.5 0.7 0.4
0.2 0.6 0.2 0.2
0.7 0.1 0.8 0.2
0.5 0.5 0.5 0.5
0.2 0.5 0.3 0.6
0.3 0.5 0.4 0.1
2 3 1
*/