最小割三问

离散变量取值问题

有若干个变量，每个变量取值为 $v_1,v_2,\ldots,v_n$，现在要求所有变量的和最小（大），且不同变量的取值有某种限制。（详细见下文例题）

先不考虑限制，考虑用最小割刻画这个问题。

如图所示，对每一个变量都建立 $n+1$ 个点 $X_1, X_2, \ldots, X_{n+1}$：

• 从 $S$ 到 $X_1$ 建立一条边权为 $\infty$ 的边；
• 从 $X_{n+1}$ 到 $T$ 建立一条边权为 $\infty$ 的边；
• 从 $X_{i}$ 到 $X_{i+1}$ 建立一条边权为 $v_{i}$ 的边；
• 从 $X_{i+1}$ 到 $X_{i}$ 建立一条边权为 $\infty$ 的边。

这样我们保证了，每个变量所构造出的一条链上，在最小割中有且仅有一条边被割掉，被割掉的边的边权就代表了我们为这个变量的取值。

证明：

• 存在性：
  如果没有边被割，那么显然存在 $S\to T$ 的路径，矛盾。
  如果不加反向边存在一个割一条边的割，加上反向边依然存在这个割。

• 唯一性：
  假设存在两条边被割，即 $X_{i}\to X_{i+1}$ 和 $X_{j}\to X_{j+1}\ (i<j)$。
  我们知道，对于一条最小割中的割边 $(u,v)$，在被割完的图中一定存在 $S\to u, v\to T$ 的路径（否则这条边不割也行）。
  那么我们可以得出存在路径 $S\to X_{j+1}, X_{i+1}\to T$。因为无穷的边不会被割掉，所以还存在路径 $X_{j+1}\to X_{i+1}$，所以存在 $S\to T$ 的路径，矛盾！

这样我们就证明了有且仅有一条边被割掉。

知道了这样的基本模型，我们来看一道例题。

[RC-02] 开门大吉

洛谷P6054 [RC-02] 开门大吉

我们转化到刚刚的模型上，这题的变量就是 $n$ 个选手每个人做的题目编号。

• 有 $n$ 个变量，每个变量 $X$ 有 $m$ 个取值，设变量 $X$ 选取的取值编号为 $f[X]\in [1,m]$。
• 有 $y$ 条限制，形如对于两个变量 $X,Y$，有 $f[X]\ge f[Y]+k$。($k$ 不一定是正数)
• 所有变量和最小。

我们考虑如何处理这个限制，事实上，如果要让 $f[X]\ge f[Y]+k$，只需要对于所有 $i=1,2,\ldots,m+1$，从 $Y_i$ 向 $X_{i+k}$ 连边权为 $\infty$ 的边即可。（如果 $i+k<0$ 或者 $i+k>m+1$ 就不连）。

为什么：
还是从最小割的角度出发考虑：

如果变量 $Y$ 选择了第 $p$ 个，那么我们知道 $Y_1\sim Y_{p}$ 被划分给了 $S$，$Y_{p+1}\sim Y_{m+1}$ 被划分给了 $T$。

记得我们从 $Y_i$ 连出的边权为 $\infty$ 的边吗？
我们知道，如果一个被划分给 $S$ 的点连出了一条边权为 $\infty$ 的边，那么这条边的终点一定也划分给 $S$（否则就割掉了一条边权为无穷的边）。

因此，$X_{1}\sim X_{p+k}$ 一定划分给了 $S$，换句话说 $f[X]\ge p+k$（想一想，为什么？），我们就完成了这个限制。（如果 $p+k<1$，那么 $X$ 任取，我们也没有限制到任何 $X$ 的取值，也成立）

---

来看一个例子：若 $m=3,k=-1$，最后的图就是这样的。

若 $f[Y]=3$，那么我们知道 $f[X]\ge 2$，反应到割上就是 $X_1,X_2$ 被强制划分给了 $S$ 集合。

因此 $f[X]$ 只能等于 $2$ 或 $3$。

参考代码（注意dinic里面如果流量大于 INF 就直接返回，要不然会超时）：

#include<bits/stdc++.h>
using namespace std;

using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define unq(x) (x).erase(unique(all((x))),(x).end())
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define mem0(x) memset((x),0,sizeof(x))

const double INF = 1e15;
template<typename Cap> struct Dinic{
    struct Edge{int u,v;Cap c,f;};
    int n;
    vector<Edge> edges;
    vector<vector<int>> G;
    vector<int> dis,cur;
    explicit Dinic(int _n):n(_n+1),G(_n+1),dis(_n+1),cur(_n+1){}

    int s,t;
    void add_edge(int u,int v,Cap w){
        edges.push_back(Edge{u,v,w,0}),edges.push_back(Edge{v,u,0,0});
        int m = edges.size();
        G[u].push_back(m-2),G[v].push_back(m-1);
    }

    bool bfs(){
        vector<bool> vis(dis.size());
        dis[s]=0;vis[s]=1;
        queue<int> q;
        q.push(s);
        while(q.size()){
            int u=q.front();q.pop();
            for(auto o:G[u]){
                const auto& e = edges[o];
                if(!vis[e.v] && (e.c-e.f)>0){
                    vis[e.v]=1;
                    dis[e.v]=dis[u]+1;
                    q.push(e.v);
                }
            }
        }
        return vis[t];
    }

    Cap dfs(int u,Cap maxflow){
        if(u==t || maxflow<1e-10)return maxflow;
        Cap flow = 0;
        for(int& i=cur[u];i<G[u].size();i++){
            auto& e=edges[G[u][i]];
            if(dis[e.v] != dis[e.u]+1)continue;
            Cap f = dfs(e.v,min(maxflow,e.c-e.f));
            flow+=f;
            maxflow-=f;
            e.f+=f;
            edges[G[u][i]^1].f-=f;
            if(maxflow<1e-10)return flow;
        }
        return flow;
    }
    Cap flow(int _s,int _t){
        s=_s,t=_t;
        Cap flow = 0;
        while(bfs() && flow < INF){
            fill(cur.begin(), cur.end(), 0);
            flow += dfs(s,numeric_limits<Cap>::max());
        }
        return flow;
    }
};

void solve(){
    int n,m,p,y;
    cin>>n>>m>>p>>y;

    auto id = [&](int i,int j){
        return (i-1)*(m+1)+j+1;
    };

    int s = 0, t = (m+1)*n+1;
    Dinic<double> g((m+1)*n+1);
    for(int i=1;i<=n;i++){
        g.add_edge(s,id(i,0),INF);
        g.add_edge(id(i,m),t,INF);
    }

    vector<int> c(n+1);
    for(int i=1;i<=p;i++)cin>>c[i];

    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            double v = 0;
            double prod_p = 1;
            for(int k=1;k<=p;k++){
                double prob; cin>>prob;
                prod_p *= prob;
                v += c[k] * prod_p;
            }
            g.add_edge(id(i,j-1),id(i,j),v);
            g.add_edge(id(i,j),id(i,j-1),INF);
        }
    }

    
    while(y--){
        int i,j,k;cin>>i>>j>>k;
        for(int x=0;x<=m;x++){
            if(x+k<0 || x+k>m)continue;
            g.add_edge(id(j,x), id(i,x+k), INF);
        }
    }      


    auto res = g.flow(s,t);
    if(res>=INF)cout<<-1<<'\n';
    else cout<<res<<'\n';
}

int main(){
    cout<<fixed<<setprecision(4);

    ios::sync_with_stdio(0);cin.tie(0);

    int T;cin>>T;
    while(T--)solve();

    return 0;
}

[HNOI2013] 切糕

洛谷P3227 [HNOI2013] 切糕
是上题的弱化版，一样处理即可。

Max Vector

[ARC176E] Max Vector

设 $P = \max{X_i,Y_i,A_{i,j}} = 500$。
考虑 $X_1\sim X_N$，$Y_1\sim Y_N$ 这 $2N$ 个变量，他们取值范围都是 $1\sim P$。

因此我们根据套路，先建立 $2N(P+1)$ 个点，具体的说，对于 $X_i$ 建立 $U_{i,1}\sim U_{i,P+1}$，对于 $Y_i$ 建立 $V_{i,1}\sim V_{i,P+1}$。

但是，我们对 $V$ 要反向建边，也就是 $S\to V_{i,P+1} \to V_{i,P} \to \ldots \to V_{i,1} \to T$。（这是为了我们表现出这个限制服务的，详见下文）

然后考虑这题给我们的所有限制：

• $X_i \ge X_{i,\text{初始}}$，$Y_i \ge Y_{i,\text{初始}}$
• $\forall i = 1,2,\ldots,M,\ \left(\bigwedge_{j=1}^N X_j\ge A_{i,j}\right)\vee\left(\bigwedge_{j=1}^N Y_j\ge A_{i,j}\right)$

对于第一个限制，我们只需要建立边权都为无穷的 $S\to U_{i,X_{i,\text{初始}}}$，$V_{i,Y_{i,\text{初始}}} \to T$ 即可。

这保证了 $U_{i,X_{i,\text{初始}}}$ 划分给 $S$，也就是 $X_i \ge X_{i,\text{初始}}$。（想一想，为什么？）
同理，另一条边保证了 $V_{i,Y_{i,\text{初始}}}$ 划分给 $T$，也就是 $Y_i \ge Y_{i,\text{初始}}$（理由同上）

对于第二个限制，我们先转化为如果 $\exist X_j < A_{i,j},\forall k, Y_j\ge A_{i,k}$，不难发现这个是一个充要条件。

那么我们就从 $V_{j,A_{i,j}}$ 向 $U_{k,A_{i,k}}$ 建立边权为 $\infty$ 的边。

此时如果 $X_j < A_{i,j}$，那么 $U_{j,A_{i,j}}$ 就会被划分给 $T$，也就保证了所有 $V_{k,A_{i,k}}$ 被划分给 $T$，也就是 $\forall k, Y_j\ge A_{i,k}$。

问题就解决了。

回到为什么要反向建边。
我们深入思考一下无穷边 $(u,v)$ 能带来的限制：

• 如果 $u$ 被划分给 $S$，那么 $v$ 被划分给 $S$；
• 如果 $v$ 被划分给 $T$，那么 $u$ 被划分给 $T$。

而在本题中，我们需要的是如果 $X_j < A_{i,j} \implies Y_{k}\ge A_{i,k}$，此时不等号方向是反的，而无穷边只能强制让两边属于同一个集合，因此我们要挑选一个变量反向建边，这样属于同一个集合所对应的不等号就是相反的，也就解决了本题。

时间复杂度：
最大流量为 $O(NP)$ ，建了 $O(N^2M)$ 条边，复杂度就是 $O(N^3P^2M)$，足够通过本题。

（官方题解给出了一个 $O(N^2P^2M)$ 的题解，可以自行阅读）

参考代码：

#include<bits/stdc++.h>
using namespace std;

using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define unq(x) (x).erase(unique(all((x))),(x).end())
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define mem0(x) memset((x),0,sizeof(x))


const int INF = 1e9;
template<typename Cap> struct Dinic{
    struct Edge{int u,v;Cap c,f;};
    int n;
    vector<Edge> edges;
    vector<vector<int>> G;
    vector<int> dis,cur;
    explicit Dinic(int _n):n(_n+1),G(_n+1),dis(_n+1),cur(_n+1){}

    int s,t;
    void add_edge(int u,int v,Cap w){
        edges.push_back(Edge{u,v,w,0}),edges.push_back(Edge{v,u,0,0});
        int m = edges.size();
        G[u].push_back(m-2),G[v].push_back(m-1);
    }

    bool bfs(){
        vector<bool> vis(dis.size());
        dis[s]=0;vis[s]=1;
        queue<int> q;
        q.push(s);
        while(q.size()){
            int u=q.front();q.pop();
            for(auto o:G[u]){
                const auto& e = edges[o];
                if(!vis[e.v] && e.c>e.f){
                    vis[e.v]=1;
                    dis[e.v]=dis[u]+1;
                    q.push(e.v);
                }
            }
        }
        return vis[t];
    }

    Cap dfs(int u,Cap maxflow){
        if(u==t || !maxflow)return maxflow;
        Cap flow = 0;
        for(int& i=cur[u];i<G[u].size();i++){
            auto& e=edges[G[u][i]];
            if(dis[e.v] != dis[e.u]+1)continue;
            Cap f = dfs(e.v,min(maxflow,e.c-e.f));
            flow+=f;
            maxflow-=f;
            e.f+=f;
            edges[G[u][i]^1].f-=f;
            if(!maxflow)return flow;
        }
        return flow;
    }
    Cap flow(int _s,int _t){
        s=_s,t=_t;
        Cap flow = 0;
        while(bfs() && flow<INF){
            fill(cur.begin(), cur.end(), 0);
            flow += dfs(s,numeric_limits<Cap>::max());
        }
        return flow;
    }
};

const int P = 500;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n,m;cin>>n>>m;
    Dinic<int> g(n*2*(P+1)+2);
    
    auto idX = [&](int i,int j){return (i-1)*(P+1)+j;};
    auto idY = [&](int i,int j){return (i-1+n)*(P+1)+j;};
    int S=0,T=idY(n,P+1)+1;

    for(int i=1;i<=n;i++){
        int xi;cin>>xi;
        g.add_edge(S,idX(i,1),INF);g.add_edge(idX(i,P+1),T,INF);
        for(int j=1;j<=P;j++){
            g.add_edge(idX(i,j),idX(i,j+1),j);
            g.add_edge(idX(i,j+1),idX(i,j),INF);
        }
        g.add_edge(S, idX(i,xi), INF); 
    }
    
    for(int i=1;i<=n;i++){
        int yi;cin>>yi;
        g.add_edge(S,idY(i,P+1),INF);g.add_edge(idY(i,1),T,INF);
        for(int j=1;j<=P;j++){
            g.add_edge(idY(i,j+1),idY(i,j),j);
            g.add_edge(idY(i,j),idY(i,j+1),INF);
        }
        g.add_edge(idY(i,yi), T, INF); 
    }

    for(int i=1;i<=m;i++){
        vector<int> a(n+1);
        for(int j=1;j<=n;j++)cin>>a[j];
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                g.add_edge(idY(k,a[k]),idX(j,a[j]),INF);
            }
        }
    }
    
    cout << g.flow(S,T) << '\n';
    return 0;
}