POJ 3686最小費用最大フロー(分割点構築図)

考え方:この問題は難しいですね.最初はテーマの意味を間違えて、それから図面を作って答えが得られなくて、それから他の人の問題解を見て、もとは行列の点ごとにまだn点に分解してやっと得ました.
そして昨夜1時間以上見て理解できなかったので、今朝来てから見て、他の人のコードで自分が考えたサンプルを実行して、それからゆっくり理解しました.
解題分析:『参考ブログ:http://blog.csdn.net/weiguang_123/article/details/7881799》
 ある機械がk個のおもちゃを処理したと仮定すると、これらのおもちゃには、2つの時間があり、1つは本当に処理された時間であり、1つは待機時間であり、待機時間は前のすべての処理されたおもちゃの時間であり、
このk個のおもちゃが本当に加工に使われる時間をa 1,a 2,a 3...akと仮定すると、各おもちゃの実際の時間は加工の時間+待ち時間であり、それぞれa 1,a 1+a 2,a 1+a 2+a 3.......a 1+a 2+...akである.和を求めるとa 1*k+a 2*(k-1)+a 3*(k-2)....+ak
       このとき、おもちゃごとに実際の時間を分けて計算して和を求めることができることに気づきました.
       機械ごとに最大n個の玩具を扱うことができるので、n個の点に分解することができ、1~nはそれぞれある玩具がこの機械の上で最後から数番目に加工されたものを表し、 そこで、各玩具iについて、機械jで取り外した各点kについて、z[i][j]*kの重み値のエッジを接続する.
      建図:ソース送金ポイントを確立し、ソースポイントと注文ごとの流量は1で、費用は0です.注文と各機械が分解した点kの確立流量は1で、費用はMij*kである.
kと送金点の確立流量は1で、費用は0で、最小費用の最大流を求めればよい.神様、この模型を建ててください.
私が考えている例は次のとおりです.
3  4
100 100 100 1 99 99 99 2 98 98 98 3
1+(1+2)+(1+2+3)=10で、上の解題で分析すると:1*3+2*2+3=10になるので、1,2,3という点は3つの点に分解され、1は:1,1*2,1*3に分解されます.2分解:2,2*2,2*3;3は、3、3*2、3*3に分解されます.したがって、ここで取る最良の経路は、1の点を1*3、2の点を2*2、3の点を3とすることである.つまり、4番目の機械で3を先に加工し、2番目の加工を2、3番目の加工を1とするので、答えは10と口算と同じで、建図は最小費用最大フローで求めることができる.

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define maxn 300005
struct
{
    int v,w,c,next,re;
    //re       ,c   ,w   
} e[maxn];
int n,cnt;
int head[maxn],que[maxn*8],pre[maxn],dis[maxn];
bool vis[maxn];
void add(int u, int v, int w, int c)
{
    e[cnt].v=v,e[cnt].w=w,e[cnt].c=c;
    e[cnt].next=head[u];
    e[cnt].re=cnt+1,head[u]=cnt++;
    e[cnt].v=u,e[cnt].w=0,e[cnt].c=-c;
    e[cnt].next=head[v];
    e[cnt].re=cnt-1,head[v]=cnt++;
}
bool spfa()
{
    int i, l = 0, r = 1;
    for(i = 0; i <= n; i ++)
        dis[i] = INF,vis[i] = false;
    dis[0]=0,que[0]=0,vis[0]=true;
    while(l<r)
    {
        int u=que[l++];
        for(i=head[u];i!=-1;i=e[i].next)
        {
            int v = e[i].v;
            if(e[i].w&&dis[v]>dis[u]+e[i].c)
            {
                dis[v] = dis[u] + e[i].c;
                pre[v] = i;
                if(!vis[v])
                {
                    vis[v] = true;
                    que[r++] = v;
                }
            }
        }
        vis[u] = false;
    }
    return dis[n]!=INF;
}
int change()
{
    int i,p,sum=INF,ans=0;
    for(i=n;i!=0;i=e[e[p].re].v)
    {//e[e[p].re].v     ,    add spfa
        p=pre[i];//p       
        sum=min(sum,e[p].w);
    }
    for(i=n;i!=0;i=e[e[p].re].v)
    {
        p=pre[i];
        e[p].w-=sum;
        e[e[p].re].w+=sum;
        ans+=sum*e[p].c;//c          ，       。
    }
    return ans;
}
int EK()
{
    int sum=0;
    while(spfa()) sum+=change();
    return sum;
}
void init()
{
    mem(head,-1),mem(pre,0),cnt=0;
}
int a[51][51];
int main()
{
    //freopen("1.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int N,M,i,j,k;
        init();
        scanf("%d%d",&N,&M);
        for(i=1;i<=N;i++)
            for(j=1;j<=M;j++)
                scanf("%d",&a[i][j]);
        for(i=1;i<=N;i++)
            add(0,i,1,0);
        for(i=1;i<=N;i++)
            for(j=1;j<=M;j++)
                for(k=1;k<=N;k++)
                    add(i,N+(j-1)*N+k,1,a[i][j]*k);
        for(j=1;j<=M;j++)
            for(k=1;k<=N;k++)
                add(N+(j-1)*N+k,N+N*M+1,1,0);
        n=N+N*M+1;
        printf("%.6f
",EK()*1.0/N);
    }
    return 0;
}