[POJ 2112] | Eurce's Blog

二分 + 最大流

题意是，有向图上有nm个终点和nc个源点，终点和源点间的边有距离d，每个终点最多可以和f个源点相连，设当所有源点都和某个终点相连时最大距离的边为mxd，求mxd最小可以是多少。

首先还是将问题转化为判定问题：对于边距离最多为md的情况，判是否存在一个匹配方案。具体的判断方式可以用最大流，方法是引入超级源点S连每个源点，距离为0，流量为1，每个终点连超级终点，距离为0，流量为f，源点和终点间的边流量为正无穷。每次求最大流时，忽略d>md的边，并且仅当求得的最大流值等于nc时判为可行。

另外这题给出的源点和终点间的边用了一个邻接表来描述，还要跑一次floyd来求出实际最小距离，然后也没有其他难点了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int nm,nc,f,hd[232],el,b[232],mxf[232],pl[232],S=0,E=231;
int d[232][232],hdb[232],elb,stk[232],sl;

struct EE
{
    int v,f,d,p;
}e[12460],eb[12460];

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

void init()
{
    int i,j,k,l;
    el=0;
    memset(hd,-1,sizeof hd);
    for(i=0;i<nc;i++)
        adde(S,nm+1+i,1,0);
    for(i=0;i<nm;i++)
        adde(i+1,E,f,0);
    l=nm+nc;
    for(i=0;i<l;i++)
        for(j=0;j<l;j++)
            scanf("%d",&d[i][j]);
    for(k=0;k<l;k++)
        for(i=0;i<l;i++)
            for(j=0;j<l;j++)
                if(d[i][k]&&d[k][j])
                {
                    if(!d[i][j])
                        d[i][j]=d[i][k]+d[k][j];
                    else
                        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
                }
    for(i=0;i<nm;i++)
        for(j=nm;j<nm+nc;j++)
            if(d[i][j])
                adde(j+1,i+1,0x7fffffff,d[i][j]);
    elb=el;
    memcpy(hdb,hd,sizeof hdb);
    memcpy(eb,e,sizeof eb);
}

int chk(int d)
{
    int i,j,k,l,sf=0;
    pl[S]=-1;
    el=elb;
    memcpy(hd,hdb,sizeof hd);
    memcpy(e,eb,sizeof e);
    while(1)
    {
        memset(mxf,0,sizeof mxf);
        mxf[S]=0x7fffffff;
        b[S]=1;
        stk[sl++]=S;
        while(sl)
        {
            i=stk[--sl];
            b[i]=0;
            for(l=hd[i];l!=-1;l=e[l].p)
            {
                j=e[l].v;
                k=min(mxf[i],e[l].f);
                if(k<=mxf[j]||e[l].d>d)
                    continue;
                mxf[j]=k;
                pl[j]=l;
                if(!b[j])
                {
                    b[j]=1;
                    stk[sl++]=j;
                }
            }
        }
        if(!mxf[E])
            break;
        sf+=mxf[E];
        for(l=pl[E];l!=-1;l=pl[e[l^1].v])
        {
            e[l].f-=mxf[E];
            e[l^1].f+=mxf[E];
        }
    }
    return sf==nc;
}

void solve()
{
    int l,h,m;
    for(l=1,h=10000;l<h;)
    {
        m=l+h>>1;
        if(chk(m))
            h=m;
        else
            l=m+1;
    }
    printf("%d\n",l);
}

int main()
{
    while(~scanf("%d%d%d",&nm,&nc,&f))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int nm,nc,f,hd[232],el,b[232],mxf[232],pl[232],S=0,E=231;

int d[232][232],hdb[232],elb,stk[232],sl;

struct EE

{

int v,f,d,p;

}e[12460],eb[12460];

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

{

e[el].v=v; e[el].f=f; e[el].d=d; e[el].p=hd[u]; hd[u]=el++;

e[el].v=u; e[el].f=0; e[el].d=d; e[el].p=hd[v]; hd[v]=el++;

}

void init()

{

int i,j,k,l;

el=0;

memset(hd,-1,sizeof hd);

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

adde(S,nm+1+i,1,0);

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

adde(i+1,E,f,0);

l=nm+nc;

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

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

scanf("%d",&d[i][j]);

for(k=0;k<l;k++)

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

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

if(d[i][k]&&d[k][j])

{

if(!d[i][j])

d[i][j]=d[i][k]+d[k][j];

else

d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

}

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

for(j=nm;j<nm+nc;j++)

if(d[i][j])

adde(j+1,i+1,0x7fffffff,d[i][j]);

elb=el;

memcpy(hdb,hd,sizeof hdb);

memcpy(eb,e,sizeof eb);

}

int chk(int d)

{

int i,j,k,l,sf=0;

pl[S]=-1;

el=elb;

memcpy(hd,hdb,sizeof hd);

memcpy(e,eb,sizeof e);

while(1)

{

memset(mxf,0,sizeof mxf);

mxf[S]=0x7fffffff;

b[S]=1;

stk[sl++]=S;

while(sl)

{

i=stk[--sl];

b[i]=0;

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

{

j=e[l].v;

k=min(mxf[i],e[l].f);

if(k<=mxf[j]||e[l].d>d)

continue;

mxf[j]=k;

pl[j]=l;

if(!b[j])

{

b[j]=1;

stk[sl++]=j;

}

if(!mxf[E])

break;

sf+=mxf[E];

for(l=pl[E];l!=-1;l=pl[e[l^1].v])

{

e[l].f-=mxf[E];

e[l^1].f+=mxf[E];

}

return sf==nc;

}

void solve()

{

int l,h,m;

for(l=1,h=10000;l<h;)

{

m=l+h>>1;

if(chk(m))

h=m;

else

l=m+1;

}

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

}

int main()

{

while(~scanf("%d%d%d",&nm,&nc,&f))

{

init();

solve();

}

return 0;

}