自动搬运

查看原文

来自洛谷，原作者为

	Aranea晨曦 2018.4.14 - 2024.3.3 | Goodbye OI, hello world.

搬运于2025-08-24 21:37:23，当前版本为作者最后更新于2023-02-02 12:34:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻喵喵的第一篇正经题解——
提交了，也许能过呢><

主要解释了一下为啥要这么连边

2023/3/14 update:改了错字 行=>列
@liyishui2003 /bx

首先，我们用流网络里的点表示 每一行 和 每一列 。
比如点 $i$ 表示第 $i$ 行，点 $j+n$ 表示第 $j$ 列。

对于每个格子 $(i,j)$，从第 $i$ 行的点向第 $j$ 列的点连一条容量为 $1$，权值为 $p_{i,j}$（指概率，输入的数值 $\times0.01$）的边。
这样，我们指定一个格子为黑色就相当于在流网络中使这条边满流——贡献了一个黑色格子，同时也得到了 $p_{i,j}$ 的价值。反之，没有贡献黑格子数量，也没有得到价值。
听说有个模型叫 网络流行列模型。

然后考虑每行、每列黑格子数量的限制，就是通过每行、每列的点的流量的限制。
所以只需要把源点 $S$ 与表示第 $i$ 列的点连的边的流量设为 $a_i$， 表示第 $j$ 列的点与汇点 $T$ 的连边的流量为 $b_j$ 就可以了。（当然全都反过来连也可以）
这样满流的时候第 $i$ 行的总流量是 $a_i$，第 $j$ 列的总流量是 $b_i$，刚好满足题意。

求的是选择的点权值之积最大，在网络里就是使满流的时候费用最大，所以跑最大费用最大流。

于是建图就是

• 对于每个格子 $(i,j)$，从第 $i$ 行的点向第 $j$ 列的点连一条容量为 $1$，权值为 $p_{i,j}$（指概率，输入的数值 $\times0.01$）的边。
• $S$ 向每行 $i$ 连容量 $a_i$，费用 $1$ 的边。
• 每列 $j$ 向 $T$ 连容量 $b_i$，费用 $1$ 的边。

一些具体实现的废话细节：

• $S$ 与行 $i$ 的连边、列 $j$ 与 $T$ 的连边权值是 $1$ 不是 $0$，因为要乘起来。
• 反向边的费用是 $\frac{1}{c}$ 不是 $-c$，同理。
• SPFA 的松弛是 dis[v]<dis[u]*e[i].c。
• 统计答案的时候，遍历每行连到每列的边，如果满流就是 $1$，反之为 $0$ 即可。
• 现在好像不卡常了，dinic 即使忘了加当前弧优化也过了。

code
record

#include<bits/stdc++.h>
#define in(x) scanf("%d",&x)
#define out(x) printf("%d",x)
#define outs(x) printf(x)
#define ed printf("\n")
#define ll long long
#define ull unsigned long long
#define mpr make_pair
#define pr pair<int,int>
#define qwq first
#define awa second
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fu(i,a,b) for(int i=a;i<b;++i)
#define INF 2139062143
//#define Aranea_Debug
#define N 110
#define M 100010
#define eps (1e-6)
using namespace std;
struct node
{
    int v,nxt,w;
    double c;
}e[M*2];
int head[M],cnt=1;
void add(int a,int b,int w,double c)
{
    e[++cnt].v=b;
    e[cnt].w=w,e[cnt].c=c;
    e[cnt].nxt=head[a];
    head[a]=cnt;
}
void link(int a,int b,int w,double c)
{
    if(!c)return;
    add(a,b,w,c),add(b,a,0,1.0/c);
}

int S,T,cur[M];
bool inq[M];
double dis[M];
queue<int>q;
bool spfa()
{
    memcpy(cur,head,sizeof(head));
    fo(i,0,T)dis[i]=-1;
    dis[S]=1.0;
    q.push(S);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        inq[u]=false;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int vol=e[i].w,v=e[i].v;
            if(vol>0&&dis[v]<dis[u]*e[i].c)
            {
                dis[v]=dis[u]*e[i].c;
                if(!inq[v])inq[v]=true,q.push(v);
            }
        }
    }
    return dis[T]>0;
}
bool vis[M];
int dfs(int u=S,int flow=INF)
{
    if(u==T)return flow;
    vis[u]=true;
    int rm=flow;
    for(int i=cur[u];i&&rm;i=e[i].nxt)
    {
        cur[u]=i;
        int vol=e[i].w,v=e[i].v;
        if(vol>0&&!vis[v]&&abs(dis[v]-dis[u]*e[i].c)<=eps) //精度问题/ll
        {
            int c=dfs(v,min(rm,vol));
            rm-=c,e[i].w-=c,e[i^1].w+=c;
        }
    }
    vis[u]=false;
    return flow-rm;
}
void dinic()
{
    while(spfa())
        dfs();
    return;
}

bool ans[N][N];
int main()
{
    int n,m,a,b,p;
    in(n),in(m);
    //建图
    S=0,T=n+m+1;
    fo(i,1,n)fo(j,1,m)
        in(p),link(i,j+n,1,p*0.01);
    fo(i,1,n)
        in(a),link(S,i,a,1);
    fo(i,1,m)
        in(b),link(i+n,T,b,1);
    dinic();
    //遍历
    fo(i,1,n)
        for(int j=head[i];j;j=e[j].nxt)
            if(!e[j].w)
                ans[i][e[j].v-n]=true;
    for(int i=1;i<=n;++i,puts(""))
        fo(j,1,m)
            out(ans[i][j]);
    return 0;
}