[POJ 3422] | Eurce's Blog

费用流。

好久没写网络流的题目了，敲了很久，不过还是1A了。

这题和以前qoshi推荐的DP是同类题目，但这超过了DP能求解的规模，所以只能用费用流来做了。思路是把矩阵每个元素拆点为ui和vi，并根据费用流算法的需要进行建图。然后重复k次增广操作即可。增广用的是基于栈的spfa。g++下跑了938ms。

#include<cstdio>
#include<cstring>

#define inf 0x0fffffff

int n,m,hd[5000],el,b[5000],f[5000],p[5000],sm,ed;
int stk[5000],sl;

struct E
{
    int u,v,c,f,p;
}e[50000];

inline void adde(int u,int v,int c,int f)
{
    e[el].u=u; e[el].v=v; e[el].c=c; e[el].f=f;
    e[el].p=hd[u]; hd[u]=el++;
}

void sa(int ui,int uj,int f)
{
    int i,j,k,l;
    i=(ui*n+uj)*2;
    j=i+1;
    adde(i,j,1,f);
    adde(j,i,0,-f);
    adde(i,j,inf,0);
    adde(j,i,0,0);
    if(ui<n-1)
    {
        k=i+2*n;
        adde(j,k,inf,0);
        adde(k,j,0,0);
    }
    if(uj<n-1)
    {
        k=i+2;
        adde(j,k,inf,0);
        adde(k,j,0,0);
    }
}

void init()
{
    int i,j,k,l;
    el=sm=0;
    memset(hd,-1,sizeof hd);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            scanf("%d",&k);
            sa(i,j,k);
        }
    ed=((n-1)*n+n-1)*2+1;
}

void solve()
{
    int i,j,k,l;
    while(m--)
    {
        sl=0;
        memset(b,0,sizeof b);
        memset(f,-1,sizeof f);
        stk[sl++]=0;
        b[0]=1;
        f[0]=0;
        while(sl)
        {
            i=stk[--sl];
            b[i]=0;
            for(l=hd[i];l!=-1;l=e[l].p)
            {
                if(e[l].c==0) continue;
                j=e[l].v;
                if(f[i]+e[l].f>f[j])
                {
                    f[j]=f[i]+e[l].f;
                    p[j]=l;
                    if(!b[j])
                    {
                        b[j]=1;
                        stk[sl++]=j;
                    }
                }
            }
        }
        sm+=f[ed];
        for(i=ed;i;i=j)
        {
            l=p[i];
            j=e[l].u;
            e[l].c--;
            e[l^1].c++;
        }
    }
    printf("%d\n",sm);
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

#include<cstdio>

#include<cstring>

#define inf 0x0fffffff

int n,m,hd[5000],el,b[5000],f[5000],p[5000],sm,ed;

int stk[5000],sl;

struct E

{

int u,v,c,f,p;

}e[50000];

inline void adde(int u,int v,int c,int f)

{

e[el].u=u; e[el].v=v; e[el].c=c; e[el].f=f;

e[el].p=hd[u]; hd[u]=el++;

}

void sa(int ui,int uj,int f)

{

int i,j,k,l;

i=(ui*n+uj)*2;

j=i+1;

adde(i,j,1,f);

adde(j,i,0,-f);

adde(i,j,inf,0);

adde(j,i,0,0);

if(ui<n-1)

{

k=i+2*n;

adde(j,k,inf,0);

adde(k,j,0,0);

}

if(uj<n-1)

{

k=i+2;

adde(j,k,inf,0);

adde(k,j,0,0);

}

void init()

{

int i,j,k,l;

el=sm=0;

memset(hd,-1,sizeof hd);

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

for(j=0;j<n;j++)

{

scanf("%d",&k);

sa(i,j,k);

}

ed=((n-1)*n+n-1)*2+1;

}

void solve()

{

int i,j,k,l;

while(m--)

{

sl=0;

memset(b,0,sizeof b);

memset(f,-1,sizeof f);

stk[sl++]=0;

b[0]=1;

f[0]=0;

while(sl)

{

i=stk[--sl];

b[i]=0;

for(l=hd[i];l!=-1;l=e[l].p)

{

if(e[l].c==0) continue;

j=e[l].v;

if(f[i]+e[l].f>f[j])

{

f[j]=f[i]+e[l].f;

p[j]=l;

if(!b[j])

{

b[j]=1;

stk[sl++]=j;

}

sm+=f[ed];

for(i=ed;i;i=j)

{

l=p[i];

j=e[l].u;

e[l].c--;

e[l^1].c++;

}

printf("%d\n",sm);

}

int main()

{

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

{

init();

solve();

}

return 0;

}