Gym - 102346G Getting Confidence 最小费用最大流

题意：n*n的格子，每个格子上有一个数，要求每行每列都只能拿一个数，使得乘积最大，然后输出每列选择的是第几行的数。

如果是加法的话，那么很明显，就是一个网络流。可是，现在是乘法怎么办，很简单，直接取log，那么乘法便转换成了加法，然后就可以建图。

每行每列只能取一个数，就相当于行列是拆开的点，因为需要输出的是列的信息，那么源点向每一列建一条流量为1，费用为0的边，而每一行向汇点建一条流量为1，费用为0的边。

再对于每个格子，每一列向它这一列的格子建一条流量为1，费用为0的点，而每个格子向它所在的行建一条流量为1，费用为-log(格子上的数)的边。

最后跑一遍最小费用最大流，看一下每一列的那条边流量为0

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #include<algorithm>

 using namespace std;

 const int N=2e4+,M=1e6+,inf=1e9+;

 struct Side{

     int v,ne,w;

     double val;

 }S[M<<];

 double dis[N];

 int n,sn,sb,se,head[N],vis[N],flow[N],lu[N];

 void init(){

     sn=;

     sb=;se=n*n+*n+;

     for(int i=sb;i<=se;i++) head[i]=-;

 }

 void add(int u,int v,int w,double val){

     S[sn].w=w;S[sn].val=val;

     S[sn].v=v;S[sn].ne=head[u];

     head[u]=sn++;

 }

 void addE(int u,int v,int w,double val){

     add(u,v,w,val);add(v,u,,-val);

 }

 bool spfa(){

     queue<int> q;

     for(int i=sb;i<=se;i++){

         dis[i]=inf;

         vis[i]=;

         flow[i]=inf;

         lu[i]=-;

     }

     dis[sb]=;

     vis[sb]=;

     q.push(sb);

     int u,v;

     while(!q.empty()){

         u=q.front();q.pop();vis[u]=;

         for(int i=head[u];~i;i=S[i].ne){

             v=S[i].v;

             if(S[i].w>&&dis[v]>dis[u]+S[i].val){

                 lu[v]=i;

                 dis[v]=dis[u]+S[i].val;

                 flow[v]=min(flow[u],S[i].w);

                 if(!vis[v]){

                     vis[v]=;

                     q.push(v);

                 }

             }

         }

     }

     return dis[se]!=inf;

 }

 void mfml(){

     int ans=,ansc=;

     while(spfa()){

         ans+=flow[se];

         ansc+=flow[se]*dis[se];

         for(int i=lu[se];~i;i=lu[S[i^].v]){

             S[i].w-=flow[se];

             S[i^].w+=flow[se];

         }

     }

 }

 int main(){

     while(~scanf("%d",&n)){

         init();;

         for(int i=;i<=n;i++){

             addE(sb,n*n+n+i,,0.0);

             addE(n*n+i,se,,0.0);

         }

         for(int i=,x;i<=n;i++){

             for(int j=;j<=n;j++){

                 scanf("%d",&x);

                 addE(n*n+n+j,(i-)*n+j,,0.0);

                 addE((i-)*n+j,n*n+i,,-log(1.0*x));

             }

         }

         mfml();

         for(int i=;i<=n;i++)

             for(int j=head[n*n+n+i];~j;j=S[j].ne){

                 if(S[j].w||S[j].v==sb) continue;

                 printf("%d%c",(S[j].v-)/n+," \n"[i==n]);

                 break;

             }

     }

     return ;

 }

log转乘为加