[POJ 1966] | Eurce's Blog

最小点割集

题意：给出一个无向图，包含n个点和m条边，问最少去掉几个点才能使图不连通。

题目数据范围很小，主要还是考察建模。将每个结点拆为两个点Si、Ei，由一条容量为1的有向边链接，对于原无向图中的每条边(i,j)，添加有向边(Ei,Sj)和(Ej,Si)，容量都为正无穷。然后枚举所有的Si为源点、Ej为汇点，将(Si,Ei)和(Sj,Ej)的容量设为正无穷，求有向图上的最小割。当最小割值为n-1时，原图最小点割集大小为n，其余情况最小点割集大小等于最小割值。这个算法复杂度是O(n^2*maxflow())也即大概是O(n^5)的，按理说n=50时应该是会TLE的……但貌似标准解法就是如此，只能说题目数据确实较弱。

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

int n,m,el,hd[100],mxf[100],b[100],pl[100],S,E;
int elb,hdb[100],stk[100],sl,ans;

struct EE
{
    int v,f,p;
}e[10000],eb[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;
    el=0;
    ans=n;
    memset(hd,-1,sizeof hd);
    for(i=0;i<n;i++)
        adde(i*2,i*2+1,1);
    for(l=0;l<m;l++)
    {
        while(getchar()!='(');
        scanf("%d",&i);
        getchar();
        scanf("%d",&j);
        getchar();
        adde(i*2+1,j*2,0x7fffffff);
        adde(j*2+1,i*2,0x7fffffff);
    }
    elb=el;
    memcpy(eb,e,sizeof eb);
    memcpy(hdb,hd,sizeof hdb);
}

int ek()
{
    int i,j,k,l,sf=0;
    pl[S]=-1;
    while(1)
    {
        memset(mxf,0,sizeof mxf);
        mxf[S]=0x7fffffff;
        b[S]=1;
        sl=0;
        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])
                    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;
}

void solve()
{
    int i,j,fs;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i==j)
                continue;
            S=i*2;
            E=j*2+1;
            el=elb;
            memcpy(hd,hdb,sizeof hd);
            memcpy(e,eb,sizeof e);
            e[i*2].f=0x7fffffff;
            e[j*2].f=0x7fffffff;
            fs=ek();
            if(fs==n-1)
                fs++;
            ans=min(ans,fs);
        }
    }
    printf("%d\n",ans);
}

int main()
{
    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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,el,hd[100],mxf[100],b[100],pl[100],S,E;

int elb,hdb[100],stk[100],sl,ans;

struct EE

{

int v,f,p;

}e[10000],eb[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;

el=0;

ans=n;

memset(hd,-1,sizeof hd);

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

adde(i*2,i*2+1,1);

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

{

while(getchar()!='(');

scanf("%d",&i);

getchar();

scanf("%d",&j);

getchar();

adde(i*2+1,j*2,0x7fffffff);

adde(j*2+1,i*2,0x7fffffff);

}

elb=el;

memcpy(eb,e,sizeof eb);

memcpy(hdb,hd,sizeof hdb);

}

int ek()

{

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

pl[S]=-1;

while(1)

{

memset(mxf,0,sizeof mxf);

mxf[S]=0x7fffffff;

b[S]=1;

sl=0;

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

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;

}

void solve()

{

int i,j,fs;

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

{

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

{

if(i==j)

continue;

S=i*2;

E=j*2+1;

el=elb;

memcpy(hd,hdb,sizeof hd);

memcpy(e,eb,sizeof e);

e[i*2].f=0x7fffffff;

e[j*2].f=0x7fffffff;

fs=ek();

if(fs==n-1)

fs++;

ans=min(ans,fs);

}

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

}

int main()

{

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

{

init();

solve();

}

return 0;

}