题意分析

这道题目是关于电缆电视网络中继器网络的连通性和安全系数的计算。题目要求我们根据给定的中继器数量和连接关系，计算网络的安全系数。安全系数的定义如下： 完全连通网络：如果无论移除多少个中继器，网络始终保持连通，则安全系数等于中继器的数量（即f = n）。 非完全连通网络：如果网络在移除某些中继器后会断开，则安全系数为使网络断开所需移除的最小中继器数量。

解题思路

1.输入处理： 读取每个数据集的中继器数量$n$和电缆数量$m$。读取$m$对电缆连接关系$(u, v)$，表示中继器$u$和$v$之间的连接。 特殊情况处理： 如果n = 0或n = 1，网络天然连通，安全系数为n。

如果m = 0且n > 1，网络不连通，安全系数为0。

2.网络连通性检查：

使用并查集（Union-Find）或深度优先搜索（DFS）来检查网络的初始连通性。 如果初始网络不连通，安全系数为0。

3.安全系数计算：

如果初始网络连通，需要计算移除某些中继器后网络断开的最小中继器数量。

对于每一对不同的中继器(i, j)，计算从i到j的最小顶点割集（即移除最少数量的中继器使得i和j不连通）。

所有(i, j)对的最小顶点割集中的最小值即为网络的安全系数。

4.最小顶点割集计算：

将每个中继器拆分为两个节点（入点和出点），并在它们之间添加容量为1的边。

对于每条电缆$(u, v)$，添加双向边$(u的出点, v的入点)和(v的出点, u的入点)$，容量为无穷大。

使用最大流算法（如ISAP）计算从i的出点到j的入点的最大流，即为(i, j)的最小顶点割集。

5.输出结果：

如果所有$(i, j)$对的最小顶点割集均大于等于n，则安全系数为n。 否则，安全系数为所有$(i, j)$对的最小顶点割集中的最小值。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 180
#define edge 10080
#define inf 0x3f3f3f3f
int first[maxn],dis[maxn],num[maxn];
int ww[edge],nxt[edge],vv[edge];
int e,NN,n,m;
struct Edge
{
	int u, v;
}cur[edge];
inline int min(int a,int b)
{
	return a>b?b:a;
}
void addEdge(int u,int v,int w)
{
	vv[e] = v;	ww[e] = w;		nxt[e] = first[u];	first[u] = e++;
	vv[e] = u;	ww[e] = 0;		nxt[e] = first[v];		first[v] = e++;
}
int dfs(int u,int s,int d,int cost)
{
	if(u == d)	return cost;
	int _min = NN;
	int ans = 0;
	for(int i = first[u];i != - 1;i = nxt[i])
	{
		int v = vv[i];
		if(ww[i])
		{
			if(dis[v] + 1 == dis[u])
			{
				int t = dfs(v,s,d,min(ww[i],cost));
				ww[i] -= t;
				ww[i^1] += t;
				cost -= t;
				ans += t;
				if(dis[s] == NN)		return ans;
				if(!cost)	break;
			}
			if(_min > dis[v])		_min = dis[v];
		}
	}
	if(!ans)
	{
		if(--num[dis[u]] == 0)	dis[s] = NN;
		dis[u] = _min + 1;
		++num[dis[u]];
	}
	return ans;
}
int isap(int s,int d)
{
	memset(dis,0,sizeof(dis));
	memset(num,0,sizeof(num));
	num[0] = NN;
	int ans = 0;
	while(dis[s] < NN)
		ans += dfs(s,s,d,inf);
	return ans;
}
void build()
{
	memset(first,-1,sizeof(first));
	e = 0;
	for(int i = 1;i <= m;i++)
	{
		addEdge(2*cur[i].u,2*cur[i].v-1,inf);
		addEdge(2*cur[i].v,2*cur[i].u-1,inf);
	}
	for(int i = 1;i <= n;i++)
	{
		addEdge(2*i-1,2*i,1);
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	while(scanf("%d%d",&n,&m)==2)
	{
		if(m == 0)	
		{
			if(n > 1)printf("%d\n",0);
			else printf("%d\n",n);
			continue;
		}
		memset(first,-1,sizeof(first));
		NN = 2*n;
		for(int i = 1;i <= m;i++)
		{
			while(getchar()!='(');
			scanf("%d",&cur[i].u);
			getchar();
			scanf("%d",&cur[i].v);
			getchar();
			cur[i].u++;cur[i].v++;
		}
		int ans = inf;
		for(int i = 1;i <= n;i++)
		{
			for(int j = 1;j <= n;j++)
			{
				if(i == j)	continue;
				build();
				ans = min(ans,isap(2*i,2*j-1));
			}
		}
		if(ans == inf)	ans = n;
		printf("%d\n",ans);
	}
	return 0;
}