[POJ 2289] | Eurce's Blog

二分 + 最大流

输入为n、m，分别表示有n个点，每个点可以属于m种分类里面的某几种，将n个点分类（使每个点仅属于某一类）后，设最大的类里含有g个点，目标就是最小化g。

模型很简单，源点到n个点有容量为1的边，n个点到各自的分类有边，m个分类到汇点各有容量为g的边。然后就是二分g的值，每次用网络流判断是否可行。

但是……到这里明明就很清晰的思路，就是给我无限TLE……在明确其他部分都没得改进后，发现是网络流算法本身太慢……一直以来都只会用EK，而可能由于做过的题目都太水了……竟然都没有被卡过TLE。这次总算栽跟头了。于是，根据这篇文章学了一下ISAP，然后用自己的数据结构来实现也很简单，一下下就AC了：

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

int n,m,el,hd[1502];
int pl[1502],d[1502],nd[1502],cl[1502],S,E;
char c;

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

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

inline int gi()
{
    while((c=getchar())<'0'||c>'9');
    int d=c-'0';
    while((c=getchar())>='0'&&c<='9')
        d=d*10+c-'0';
    return d;
}

void init()
{
    int i,j,k,l;
    el=0;
    S=n+m;
    E=n+m+1;
    memset(hd,-1,sizeof hd);
    for(i=0;i<m;i++)
        adde(i,E,0);
    for(i=0;i<n;i++)
        adde(S,m+i,1);
    for(i=0;i<n;i++)
    {
        scanf("%*s%c",&c);
        while(c!='\n')
        {
            j=gi();
            adde(m+i,j,1);
        }
    }
    memcpy(eb,e,el*sizeof(EE));
}

bool bfs()
{
    int i,j,k,l;
    memset(d,0,sizeof d);
    queue<int> Q;
    Q.push(E);
    while(!Q.empty())
    {
        i=Q.front(); Q.pop();
        for(l=hd[i];l!=-1;l=e[l].p)
        {
            j=e[l].v;
            k=e[l^1].f;
            if(d[j]||!k)
                continue;
            d[j]=d[i]+1;
            Q.push(j);
        }
    }
    return d[S];
}

int aug()
{
    int k,l;
    for(l=pl[E],k=0x7fffffff;l!=-1;l=pl[e[l^1].v])
        k=min(k,e[l].f);
    for(l=pl[E];l!=-1;l=pl[e[l^1].v])
    {
        e[l].f-=k;
        e[l^1].f+=k;
    }
    return k;
}

bool chk(int g)
{
    int i,j,k,l,sf=0;
    pl[S]=-1;
    memcpy(cl,hd,sizeof cl);
    memset(nd,0,sizeof nd);
    memcpy(e,eb,el*sizeof(EE));
    for(i=j=0;i<m;i++,j+=2)
        e[j].f=g;
    bfs();
    for(i=0;i<n+m+2;i++)
        nd[d[i]]++;
    i=S;
    while(d[S]<n+m+2)
    {
        if(i==E)
        {
            sf+=aug();
            i=S;
        }
        k=0;
        for(l=cl[i];l!=-1;l=e[l].p)
        {
            j=e[l].v;
            if(e[l].f&&d[j]==d[i]-1)
            {
                k=1;
                pl[j]=cl[i]=l;
                i=j;
                break;
            }
        }
        if(!k)
        {
            int k=m+n+1;
            for(l=hd[i];l!=-1;l=e[l].p)
                if(e[l].f)
                    k=min(k,d[e[l].v]);
            if(--nd[d[i]]==0)
                break;
            nd[d[i]=k+1]++;
            cl[i]=hd[i];
            if(pl[i]!=-1)
                i=e[pl[i]^1].v;
        }
    }
    return sf==n;
}

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,el,hd[1502];

int pl[1502],d[1502],nd[1502],cl[1502],S,E;

char c;

struct EE

{

int v,f,p;

}e[1000000],eb[1000000];

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

{

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

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

}

inline int gi()

{

while((c=getchar())<'0'||c>'9');

int d=c-'0';

while((c=getchar())>='0'&&c<='9')

d=d*10+c-'0';

return d;

}

void init()

{

int i,j,k,l;

el=0;

S=n+m;

E=n+m+1;

memset(hd,-1,sizeof hd);

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

adde(i,E,0);

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

adde(S,m+i,1);

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

{

scanf("%*s%c",&c);

while(c!='\n')

{

j=gi();

adde(m+i,j,1);

}

memcpy(eb,e,el*sizeof(EE));

}

bool bfs()

{

int i,j,k,l;

memset(d,0,sizeof d);

queue<int> Q;

Q.push(E);

while(!Q.empty())

{

i=Q.front(); Q.pop();

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

{

j=e[l].v;

k=e[l^1].f;

if(d[j]||!k)

continue;

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

Q.push(j);

}

return d[S];

}

int aug()

{

int k,l;

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

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

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

{

e[l].f-=k;

e[l^1].f+=k;

}

return k;

}

bool chk(int g)

{

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

pl[S]=-1;

memcpy(cl,hd,sizeof cl);

memset(nd,0,sizeof nd);

memcpy(e,eb,el*sizeof(EE));

for(i=j=0;i<m;i++,j+=2)

e[j].f=g;

bfs();

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

nd[d[i]]++;

i=S;

while(d[S]<n+m+2)

{

if(i==E)

{

sf+=aug();

i=S;

}

k=0;

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

{

j=e[l].v;

if(e[l].f&&d[j]==d[i]-1)

{

k=1;

pl[j]=cl[i]=l;

i=j;

break;

}

if(!k)

{

int k=m+n+1;

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

if(e[l].f)

k=min(k,d[e[l].v]);

if(--nd[d[i]]==0)

break;

nd[d[i]=k+1]++;

cl[i]=hd[i];

if(pl[i]!=-1)

i=e[pl[i]^1].v;

}

return sf==n;

}

void solve()

{

int l,h,mid;

for(l=n/m,h=n;l<h;)

{

mid=l+h>>1;

if(chk(mid))

h=mid;

else

l=mid+1;

}

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

}

int main()

{

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

{

init();

solve();

}

return 0;

}