????? 無(wú)向(有向)圖G中，給定源點(diǎn)s和終點(diǎn)t，至少要?jiǎng)h去多少個(gè)點(diǎn)(具體一點(diǎn)，刪哪些點(diǎn))，使得s和t不連通。這個(gè)問(wèn)題就是 點(diǎn)連通度 ，也叫 最小點(diǎn)割集 。

???? 一般最小點(diǎn)割轉(zhuǎn)化到最小邊割上，將原圖中的點(diǎn)v拆成v'和v''，且w(v,v'')=1。對(duì)于原圖中的有向邊(u,v)，則有w(u'',v')=INF；若是無(wú)向邊，則還要加上邊：w(v'',v')=INF。然后求以s''為源點(diǎn)，t'為匯點(diǎn)的最大流。 maxflow即為最少需要?jiǎng)h的點(diǎn)數(shù)，割邊集對(duì)應(yīng)了具體刪的點(diǎn)的一組解 。

???? 值得 注意 的是最小點(diǎn)割的解有很多，如下圖：

?

?

???? 最小點(diǎn)割的方案有4種：(4,3)，(4,1)，(2,3)，(2,1)。若按上述方法求解，最小割點(diǎn)集為(4,3)。

?

例： POJ1815

???? 題意： 給出一個(gè)圖，問(wèn)要?jiǎng)h去多少個(gè)點(diǎn)，才能使得從1到不了n。顯然這是個(gè)最小點(diǎn)割問(wèn)題。但題目又要求，如果有多種方案，輸出序號(hào)最小的一種。

???? 解： 顯然，如果s和t直接相連，則無(wú)解。求最小點(diǎn)割集方法并不難，取割邊集即可，關(guān)鍵是如何滿(mǎn)足題意"序號(hào)最小的一種"。有一種簡(jiǎn)單的貪心：從2到n-1枚舉刪除每一個(gè)點(diǎn)，看刪除之后流量是否發(fā)生變化，若變化，則這點(diǎn)就算在解中；否則恢復(fù)這個(gè)點(diǎn)。過(guò)程一直進(jìn)行到maxflow=0為止。

    #include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x7fffffff;
const int maxv = 410;
const int maxe = maxv*maxv*10;
int n;
int g[205][205];
struct Edge
{
    int v;
    int next;
    int flow;
};
Edge e[maxe];
int head[maxv],edgeNum;
int now[maxv],d[maxv],vh[maxv],pre[maxv],preh[maxv];
int result[maxv];
bool cut[maxv];

void addEdge(int a,int b,int c)
{
    e[edgeNum].v = b;
    e[edgeNum].flow = c;
    e[edgeNum].next = head[a];
    head[a] = edgeNum++;
    e[edgeNum].v = a;
    e[edgeNum].flow = 0;
    e[edgeNum].next = head[b];
    head[b] = edgeNum++;
}

void Init()
{
    edgeNum = 0;
    memset(head,-1,sizeof(head));
    memset(d,0,sizeof(d));
}

int sap(int s,int t,int n)       //源點(diǎn)，匯點(diǎn)，結(jié)點(diǎn)總數(shù)
{
    int i,x,y;
    int f,ans = 0;
    for(i = 0; i < n; i++)
        now[i] = head[i];
    vh[0] = n;
    x = s;
    while(d[s] < n)
    {
        for(i = now[x]; i != -1; i = e[i].next)
            if(e[i].flow > 0 && d[y=e[i].v] + 1 == d[x])
                break;
            if(i != -1)
            {
                now[x] = preh[y] = i;
                pre[y] = x;
                if((x=y) == t)
                {
                    for(f = INF,i=t; i != s; i = pre[i])
                        if(e[preh[i]].flow < f)
                            f = e[preh[i]].flow;
                    ans += f;
                    do
                    {
                        e[preh[x]].flow -= f;
                        e[preh[x]^1].flow += f;
                        x = pre[x];
                    }while(x!=s);
                }
            }
            else
            {
                if(!--vh[d[x]])
                    break;
                d[x] = n;
                for(i=now[x]=head[x]; i != -1; i = e[i].next)
                {
                    if(e[i].flow > 0 && d[x] > d[e[i].v] + 1)
                    {
                        now[x] = i;
                        d[x] = d[e[i].v] + 1;
                    }
                }
                ++vh[d[x]];
                if(x != s)
                    x = pre[x];
            }
    }
    return ans;
}

void makeGraph()
{
    int i,j;
    Init();
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            if(g[i][j])
            {
                addEdge(i+n,j,INF);
                addEdge(j+n,i,INF);
            }
        }
    }
    for(i = 1; i <= n; i++)
    {
        if(!cut[i])
            addEdge(i,i+n,1);
        else
            addEdge(i,i+n,0);
    }
}

int main()
{
    int i,j;
    int s,t;
    scanf("%d %d %d",&n,&s,&t);
    memset(cut,0,sizeof(cut));
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            scanf("%d",&g[i][j]);
    if(g[s][t])
    {
        printf("NO ANSWER!");
        return 0;
    }
    makeGraph();
    int flow = sap(s+n,t,2*n);
    printf("%d\n",flow);
    int cnt = 0;
    for(i = 1; i <= n && flow; i++)
    {
        if(i==s||i==t)
            continue;
        cut[i] = true;
        makeGraph();
        if(sap(s+n,t,2*n) == flow-1)
        {
            flow--;
            result[cnt++] = i;
        }
        else
            cut[i] = false;
    }
    for(i = 0; i < cnt; i++)
        printf("%d ",result[i]);
    printf("\n");
    return 0;
}
  

?

?

最小點(diǎn)割集(點(diǎn)連通度)