[POJ 3084] | Eurce's Blog

最小割

有向图上有n个结点，某些点有标记，要求对于某特定的m点，要割掉多少条边才能使从m点出发无法到达任何一个标记点。

题目数据范围很小，主要考察的还是最小割的建模，也即将图分成S、T两部分，S包含m，T包含所有标记点，求S和T间的最小割即可。

注意首先要判断是否无解，然后要合并必定可达的结点，最后用最大流即可。

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

int n,m,hd[22],el,b[22],mxf[22],pl[22],t[22],ans,S=20,E=21;
char s[3];

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

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++;
}

void init()
{
    int i,j,k,l;
    ans=el=0;
    memset(hd,-1,sizeof hd);
    memset(t,0,sizeof t);
    adde(S,m,0x7fffffff);
    for(i=0;i<n;i++)
    {
        scanf("%s%d",s,&l);
        while(l--)
        {
            scanf("%d",&j);
            adde(i,j,1);
        }
        if(s[0]=='I')
        {
            t[i]=1;
            adde(i,E,0x7fffffff);
        }
    }
}

int dfs(int i)
{
    int j,k,l;
    b[i]=1;
    for(l=hd[i];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        k=e[l].f;
        if(j==E)
            return 1;
        if(b[j]||k)
            continue;
        if(dfs(j))
            return 1;
    }
    return 0;
}

void bfs(int i)
{
    int j,k,l;
    queue<int>Q;
    memset(b,0,sizeof b);
    b[i]=1;
    Q.push(i);
    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].f;
            if(!k&&!b[j])
            {
                adde(i,j,0x7fffffff);
                b[j]=1;
                Q.push(j);
            }
        }
    }
}

void bfsr(int i)
{
    int j,k,l;
    queue<int>Q;
    memset(b,0,sizeof b);
    b[i]=1;
    Q.push(i);
    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].f;
            if(k==1&&!b[j])
            {
                adde(j,i,0x7fffffff);
                b[j]=1;
                Q.push(j);
            }
        }
    }
}

void ek()
{
    int i,j,k,l;
    pl[S]=-1;
    queue<int>Q;
    while(1)
    {
        memset(b,0,sizeof b);
        memset(mxf,0,sizeof mxf);
        mxf[S]=0x7fffffff;
        b[S]=1;
        Q.push(S);
        while(!Q.empty())
        {
            i=Q.front(); Q.pop();
            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])
                    continue;
                mxf[j]=k;
                pl[j]=l;
                if(!b[j])
                {
                    b[j]=1;
                    Q.push(j);
                }
            }
        }
        if(!mxf[E])
            break;
        ans++;
        for(l=pl[E];l!=-1;l=pl[e[l^1].v])
        {
            e[l].f-=mxf[E];
            e[l^1].f+=mxf[E];
        }
    }
}

void solve()
{
    int i;
    memset(b,0,sizeof b);
    if(dfs(m))
    {
        puts("PANIC ROOM BREACH");
        return;
    }
    bfs(m);
    for(i=0;i<n;i++)
    {
        if(t[i])
            bfsr(i);
    }
    ek();
    printf("%d\n",ans);
}

int main()
{
    scanf("%*d");
    while(~scanf("%d%d",&n,&m))
    {
        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

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,hd[22],el,b[22],mxf[22],pl[22],t[22],ans,S=20,E=21;

char s[3];

struct EE

{

int v,f,p;

}e[10000];

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++;

}

void init()

{

int i,j,k,l;

ans=el=0;

memset(hd,-1,sizeof hd);

memset(t,0,sizeof t);

adde(S,m,0x7fffffff);

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

{

scanf("%s%d",s,&l);

while(l--)

{

scanf("%d",&j);

adde(i,j,1);

}

if(s[0]=='I')

{

t[i]=1;

adde(i,E,0x7fffffff);

}

int dfs(int i)

{

int j,k,l;

b[i]=1;

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

{

j=e[l].v;

k=e[l].f;

if(j==E)

return 1;

if(b[j]||k)

continue;

if(dfs(j))

return 1;

}

return 0;

}

void bfs(int i)

{

int j,k,l;

queue<int>Q;

memset(b,0,sizeof b);

b[i]=1;

Q.push(i);

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].f;

if(!k&&!b[j])

{

adde(i,j,0x7fffffff);

b[j]=1;

Q.push(j);

}

void bfsr(int i)

{

int j,k,l;

queue<int>Q;

memset(b,0,sizeof b);

b[i]=1;

Q.push(i);

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].f;

if(k==1&&!b[j])

{

adde(j,i,0x7fffffff);

b[j]=1;

Q.push(j);

}

void ek()

{

int i,j,k,l;

pl[S]=-1;

queue<int>Q;

while(1)

{

memset(b,0,sizeof b);

memset(mxf,0,sizeof mxf);

mxf[S]=0x7fffffff;

b[S]=1;

Q.push(S);

while(!Q.empty())

{

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

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])

continue;

mxf[j]=k;

pl[j]=l;

if(!b[j])

{

b[j]=1;

Q.push(j);

}

if(!mxf[E])

break;

ans++;

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

{

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

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

}

void solve()

{

int i;

memset(b,0,sizeof b);

if(dfs(m))

{

puts("PANIC ROOM BREACH");

return;

}

bfs(m);

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

{

if(t[i])

bfsr(i);

}

ek();

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

}

int main()

{

scanf("%*d");

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

{

init();

solve();

}

return 0;

}

ps: 这也是在poj上水掉的第300题，虽然还是很弱，也稍作纪念吧。