学步园

无向图的最大独立轨。

独立轨：设A、B是无向图G的两个顶点，从A到B的两条没有公共内部顶点的路径互称为独立轨。A到B的独立轨的最大条数，记作P（A,B）。

设A、B是无向图G的两个不相邻的顶点，最少要删除多少个顶点才使得A和B不再连通？答案是P(A,B)个。

关于无向图G顶点连通度K（G）与顶点独立轨之间的关系。

Menger定理：

K(G） = |V(G)| - 1 当G是完全图。

K(G) = min(P(A,B))当G不是完全图。

求P（A,B）方法如下。

（1）为了求P（A,B），需要构造一个容量网络。

 1、原图G中的每个顶点v变成网络N中的两个顶点v'和v''，顶点v'到v''有一条弧连接，即<v',v''>，其容量为1。

 2、原图G中的每条边e = (u, v)，在网络N中有两条弧e' = <u'',v'>和e'' = <u',v''>,e'和e''的容量均为INF。 

 3、另A''为源点，B'为汇点。

（2）求从A''到B'的最大流。

（3）流出A''的一切弧的容量和sigma F(e)，即为P（A,B），所以具有流量为1的弧(v',v'')对应的顶点构成了一个割顶集，在图G中去掉这些顶点后，则A和B不再连通了。

有了求P（A,B）的算法基础，就可以得出K(G)的求解思路：首先设K（G）的初始值为INF，然后分析图G中的每一对顶点，如果A、B不相邻，则用最大流的方法求出P（A,B）和对应的割顶集。如果P（A,B）小于当前的K（G），则K（G） = P(A,B)；如此直到不相邻的顶点分析完为止，即可求出K（G)。

具体的实现时，我们可以固定一个源点，枚举每个汇点，从而求出K（G）。

实际上拆点、连边时，我们一般是把<u',u''>置1，<u'', v'>与<v'',u'>置INF。

附 POJ 1966源代码。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int MAXN = 105;
const int MAXM = 105*105;
const int INF = 0x3f3f3f3f;

struct Edge
{
	int v, next;
	int f;
}edge[MAXM];

int cnt;
int n, m;

int first[MAXN], level[MAXN];
int q[MAXN];

void init()
{
	cnt = 0;
	memset(first, -1, sizeof(first));
}

void read_graph(int u, int v, int f)
{
	edge[cnt].v = v, edge[cnt].f = f;
	edge[cnt].next = first[u], first[u] = cnt++;
	edge[cnt].v = u, edge[cnt].f = 0;
	edge[cnt].next = first[v], first[v] = cnt++;
}

int bfs(int s, int t)
{
	memset(level, 0, sizeof(level));
	level[s] = 1;
	int front = 0, rear = 1;
	q[front] = s;
	while(front < rear)
	{
		int x = q[front++];
		if(x == t) return 1;
		for(int e = first[x]; e != -1; e = edge[e].next)
		{
			int v = edge[e].v, f = edge[e].f;
			if(!level[v] && f)
			{
				level[v] = level[x] + 1;
				q[rear++] = v;
			}
		}
	}
	return 0;
}

int dfs(int u, int maxf, int t)
{
	if(u == t) return maxf;
	int ret = 0;
	for(int e = first[u]; e != -1; e = edge[e].next)
	{
		int v = edge[e].v, f = edge[e].f;
		if(level[v] == level[u] + 1 && f)
		{
			int Min = min(maxf-ret, f);
			f = dfs(v, Min, t);
			edge[e].f -= f;
			edge[e^1].f += f;
			ret += f;
			if(ret == maxf) return ret;
		}
	}
	return ret;
}

int Dinic(int s, int t)
{
	int ans = 0;
	while(bfs(s, t)) ans += dfs(s, INF, t);
	return ans;
}

void init_flow() //重置网络流为初始值
{
	for(int i = 0; i < cnt; i += 2)
	{
		edge[i].f += edge[i^1].f;
		edge[i^1].f = 0;
	}
}

void read_case()
{
	init();
	for(int i = 0; i < n; i++)
	{
		read_graph(i, i+n, 1);
	}
	for(int i = 0; i < m; i++)
	{
		int u, v;
		while(getchar() != '(' ) ;
		scanf("%d,%d)", &u, &v);
		read_graph(u+n, v, INF);
		read_graph(v+n, u, INF);
	}
}

void solve()
{
	read_case();
	int ans = INF;
	for(int i = 1; i < n; i++)
	{
		ans = min(ans, Dinic(0+n, i)); //以0''为源点，枚举其他顶点i' 
		init_flow();
	}
	if(ans == INF) ans = n;
	printf("%d\n", ans);
}

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