GYM10236 G Getting Confidence（费用流残余网络求方案）

题目链接：https://codeforces.com/gym/102346
据说是一个常见模型…蒟蒻还是头一次写到，djistra模型没改出来，就用了比较熟悉的spfa费用流。
占坑 有空详补题解。

大致题意

给一个n x m 的矩阵，其中数字都是正整数，要求每行每列只能选择一个数字，使得他们的乘积最大。输出每一列所选的行数分别是多少。

思路

首先对aij取log，将乘法转化为加法，然后根据这是个常见的约束套路。新建n+m个节点，其中n个分别代表 n 行的限制，m个代表m列的限制。从 s 向 n 行连容量为1 费用为0的边，然后 n 行向所有点连 容量为 1 费用为0 的边，然后 所有节点再向 m 列连容量为 1 费用为 log(aij) 的边，最后 m 列向 t 连容量为1 费用为0 的边。 建图结束，这样建图完成了对于每行每列只能选择一个点的限制，然后在上面跑费用流即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define maxn 105
#define maxm 11006
#define ll long long int
#define INF 0x3f3f3f3f
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
#define mem(a) memset(a,0,sizeof(a))
#define sqr(x) (x*x)
#define inf (ll)2e18+1
#define PI acos(-1)
#define mod 10007
#define auto(i,x) for(int i=head[x];i;i=ed[i].nxt)
#define ls x<<1
#define rs x<<1|1
ll read(){
    ll x=0,f=1ll;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
     while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
     return f*x;
}
int n,m,b[maxn][maxn],T;
int s,t;
struct node{int u,v,f;
double w;};
vector<node>ed;
vector<int>e[maxm];///边的标号
void addEdge(int x,int y,int z,double w)
{
    ed.push_back({x,y,z,w});
    ed.push_back({y,x,0,-w});
    int k=ed.size();///0---k-1
    e[x].push_back(k-2);
    e[y].push_back(k-1);
}
int a[maxm],p[maxm];
double dis[maxm];///a[i]:到i点的最大流量    p[i]：到i点所经过的边
bool inq[maxm];
pair<int,int> mcmf(int idt)
{
    int mc=0,mf=0;
    while(true){
        //memset(dis,idt*INF,sizeof(dis));
        inc(i,0,maxm-1)dis[i]=-1.0*1e18;
        memset(a,0,sizeof(a));
        queue<int>q;
        q.push(s);
        a[s]=INF;
        dis[s]=0;
        inq[s]=1;
        while(!q.empty()){
            int u=q.front();q.pop();inq[u]=0;
            for(int i=0;i<e[u].size();i++){
                int v=ed[e[u][i]].v;
                int f=ed[e[u][i]].f;
                double w=ed[e[u][i]].w;
                if(idt*dis[v]>idt*(dis[u]+w)&&f>0){
                    dis[v]=dis[u]+w;
                    a[v]=min(f,a[u]);
                    p[v]=e[u][i];
                    if(inq[v]==0){
                        q.push(v);
                        inq[v]=1;
                    }
                }
            }
        }
        if(a[t]==0)break;
        mf+=a[t];
        mc+=dis[t]*a[t];
        for(int i=t;i!=s;i=ed[p[i]].u){
            ed[p[i]].f-=a[t];
            ed[p[i]^1].f+=a[t];
        }
    }
    return make_pair(mf,mc);
}
int main()
{
    n=read();
    s=n*(n+2)+1;t=s+1;
    inc(i,1,n)inc(j,1,n)b[i][j]=read();
    inc(i,1,n)addEdge(s,n*n+i,1,0),addEdge(n*n+n+i,t,1,0);
    inc(i,1,n)inc(j,1,n)addEdge(n*n+i,(i-1)*n+j,1,0),addEdge((i-1)*n+j,n*n+n+j,1,log10(b[i][j]));
    mcmf(-1);
    inc(i,n*n+n+1,n*n+n+n){
        for(int j=0;j<e[i].size();j++){
            node now=ed[e[i][j]];
            if(now.v==t)continue;
            if(now.f==1)printf("%d%c",(now.v-1)/n+1,i==n*n+2*n?'\n':' ');
        }
    }
    return 0;
}
/*
3
1 15 37
42 8 25
77 2 1
*/