P2410 [SDOI2009] 最优图像

· · 题解

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

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

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，刚好满足题意。

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

于是建图就是

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

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;
}