Poj 1966 Cable TV Network【點連通度------最大流Dinic】

Cable TV Network

Time Limit: 1000MS	Memory Limit: 30000K
Total Submissions: 4656	Accepted: 2149

Description

The interconnection of the relays in a cable TV network is bi-directional. The network is connected if there is at least one interconnection path between each pair of relays present in the network. Otherwise the network is disconnected. An empty network or a network with a single relay is considered connected. The safety factor f of a network with n relays is: 

1. n, if the net remains connected regardless the number of relays removed from the net. 

2. The minimal number of relays that disconnect the network when removed. 

For example, consider the nets from figure 1, where the circles mark the relays and the solid lines correspond to interconnection cables. The network (a) is connected regardless the number of relays that are removed and, according to rule (1), f=n=3. The network (b) is disconnected when 0 relays are removed, hence f=0 by rule (2). The network (c) is disconnected when the relays 1 and 2 or 1 and 3 are removed. The safety factor is 2.

Input

Write a program that reads several data sets from the standard input and computes the safety factor for the cable networks encoded by the data sets. Each data set starts with two integers: 0<=n<=50,the number of relays in the net, and m, the number of cables in the net. Follow m data pairs (u,v), u < v, where u and v are relay identifiers (integers in the range 0..n-1). The pair (u,v) designates the cable that interconnects the relays u and v. The pairs may occur in any order.Except the (u,v) pairs, which do not contain white spaces, white spaces can occur freely in input. Input data terminate with an end of file and are correct.

Output

For each data set, the program prints on the standard output, from the beginning of a line, the safety factor of the encoded net.

Sample Input

0 0

1 0

3 3 (0,1) (0,2) (1,2)

2 0

5 7 (0,1) (0,2) (1,3) (1,2) (1,4) (2,3) (3,4)

Sample Output

1

3

2

Hint

The first data set encodes an empty network, the second data set corresponds to a network with a single relay, and the following three data sets encode the nets shown in figure 1.

Source

Southeastern Europe 2004

題目大意：

求點連通度，就是問最少去掉多少個點能夠使得剩下的圖不連通。

思路（學習摘抄自網絡）：

圖的連通度分為點連通度和邊連通度： 

（1）點連通度：隻許删點，求至少要删掉幾個點（當然，s和t不能删去，這裡保證原圖中至少有三個點）； 

（2）邊連通度：隻許删邊，求至少要删掉幾條邊。 

并且，有向圖和無向圖的連通度求法不同，是以還要分開考慮（對于混合圖，隻需将其中所有的無向邊按照 

無向圖的辦法處理、有向邊按照有向圖的辦法處理即可）。

【1】有向圖的邊連通度： 

這個其實就是最小割問題。以s為源點，t為彙點建立網絡，原圖中的每條邊在網絡中仍存在，容量為1，求該網絡的最小割（也就是最大流）的值即為原圖的邊連通度。 

【2】有向圖的點連通度： 

需要拆點。建立一個網絡，原圖中的每個點i在網絡中拆成i'與i''，有一條邊<i', i''>，容量為1 （<s', s''>和<t', t''>例外，容量為正無窮）。原圖中的每條邊<i, j>在網絡中為邊<i'', j'>， 

容量為正無窮。以s'為源點、t''為彙點求最大流，最大流的值即為原圖的點連通度。 

說明：最大流對應的是最小割。顯然，容量為正無窮的邊不可能通過最小割，也就是原圖中的邊和s、t兩個點不能删去；若邊<i, i''>通過最小割，則表示将原圖中的點i删去。

【3】無向圖的邊連通度： 

将圖中的每條邊(i, j)拆成<i, j>和<j, i>兩條邊，再按照有向圖的辦法（【1】）處理； 

【4】無向圖的點連通度： 

将圖中的每條邊(i, j)拆成<i, j>和<j, i>兩條邊，再按照有向圖的辦法（【2】）處理。

對應枚舉源點S和彙點T，跑最大流，維護最小值即可。

如果最大流跑出來的值為INF，表示圖是完全連通的，需要将所有點都去掉才行。

Ac代碼：

#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
struct node
{
    int from;
    int to;
    int w;
    int next;
}e[400000];
int n,m,ss,tt,cont;
int cur[4000];
int divv[4000];
int head[4000];
int bian[40000][2];
void add(int from,int to,int w)
{
    e[cont].to=to;
    e[cont].w=w;
    e[cont].next=head[from];
    head[from]=cont++;
}
void getmap(int sss,int ttt)
{
    ss=sss;
    tt=ttt;
    cont=0;
    memset(head,-1,sizeof(head));
    for(int i=0;i<n;i++)
    {
        add(i,i+n,1);
        add(i+n,i,0);
    }
    for(int i=0;i<m;i++)
    {
        int u=bian[i][0],v=bian[i][1];
        add(u+n,v,INF);
        add(v,u+n,0);
        add(v+n,u,INF);
        add(u,v+n,0);
    }
}
int makedivv()
{
    queue<int >s;
    memset(divv,0,sizeof(divv));
    divv[ss]=1;
    s.push(ss);
    while(!s.empty())
    {
        int u=s.front();
        if(u==tt)return 1;
        s.pop();
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].to;
            int w=e[i].w;
            if(w&&divv[v]==0)
            {
                divv[v]=divv[u]+1;
                s.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int u,int maxflow,int tt)
{
    if(u==tt)return maxflow;
    int ret=0;
    for(int &i=cur[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        int w=e[i].w;
        if(w&&divv[v]==divv[u]+1)
        {
            int f=Dfs(v,min(maxflow-ret,w),tt);
            e[i].w-=f;
            e[i^1].w+=f;
            ret+=f;
            if(ret==maxflow)return ret;
        }
    }
    return ret;
}
int Slove(int sss,int ttt)
{
    getmap(sss,ttt);
    int ans=0;
    while(makedivv()==1)
    {
        memcpy(cur,head,sizeof(head));
        ans+=Dfs(ss,INF,tt);
    }
    return ans;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(m==0)
        {
            if(n==1)printf("1\n");
            else printf("0\n");
            continue;
        }
        if(n==0)
        {
            printf("0\n");
            continue;
        }
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf(" (%d,%d)",&u,&v);
            bian[i][0]=u;
            bian[i][1]=v;
        }
        int output=INF;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                int tmp=Slove(i+n,j);
                output=min(output,tmp);
            }
        }
        if(output>=n)output=n;
        printf("%d\n",output);
    }
}