POJ 1966 Cable TV Network 图的连通度,网络流最小割
Cable TV Network
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 5047 Accepted: 2347
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
0
1
3
0
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.
问删除几个点后使得图不连通，我们可以拆点成边，对于i拆成i和i+n，权为1。和源汇点相连的权为inf，这样这些边就不会加入割中。这样我们枚举源点，汇点，求最大流，即最小割。求得的是以枚举的s,t点为源点，汇点的图不连通需要删除的点。所有枚举情况最小的即时答案。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct Dinic {
static const int MAXN = 500 + 7;
static const int MAXM = MAXN * MAXN;
static const int INF = 0x3f3f3f3f;
int n, m, s, t;
int first[MAXN], cur[MAXN], dist[MAXN], sign;
struct Node {
int to, flow, next;
} edge[MAXM * 4];
inline void init(int start, int vertex, int ss, int tt) {
n = vertex, s = ss, t = tt;
for(int i = start; i <= n; i++ ) {
first[i] = -1;
}
sign = 0;
}
inline void addEdge(int u, int v, int flow) {
edge[sign].to = v, edge[sign].flow = flow, edge[sign].next = first[u];
first[u] = sign++;
}
inline void add_edge(int u, int v, int flow) {
addEdge(u, v, flow);
addEdge(v, u, 0);
}
inline int dinic() {
int max_flow = 0;
while(bfs(s, t)) {
for(int i = 0; i <= n; i++ ) {
cur[i] = first[i];
}
max_flow += dfs(s, INF);
}
return max_flow;
}
bool bfs(int s, int t) {
memset(dist, -1, sizeof(dist));
queue<int>que;
que.push(s), dist[s] = 0;
while(!que.empty()) {
int now = que.front();
que.pop();
if(now == t) {
return 1;
}
for(int i = first[now]; ~i; i = edge[i].next) {
int to = edge[i].to, flow = edge[i].flow;
if(dist[to] == -1 && flow > 0) {
dist[to] = dist[now] + 1;
que.push(to);
}
}
}
return 0;
}
int dfs(int now, int max_flow) {
if(now == t) {
return max_flow;
}
int ans = 0, next_flow = 0;
for(int &i = cur[now]; ~i; i = edge[i].next) {
int to = edge[i].to, flow = edge[i].flow;
if(dist[to] == dist[now] + 1 && flow > 0) {
next_flow = dfs(to, min(max_flow - ans, flow));
ans += next_flow;
edge[i].flow -= next_flow;
edge[i ^ 1].flow += next_flow;
if(ans == max_flow) {
return max_flow;
}
}
}
if(ans == 0) {
return dist[now] = 0;
}
return ans;
}
} cwl;
int n, m;
int main()
{
while(~scanf("%d %d", &n, &m)) {
vector<pair<int, int> >vec;
for(int i = 1; i <= m; i++ ) {
int u, v;
scanf(" (%d,%d)", &u, &v);
u++, v++;
vec.push_back(make_pair(u, v));
}
int ans = cwl.INF;
for(int s = 1; s <= n; s++ ) {
for(int t = s + 1; t <= n; t++ ) {
cwl.init(0, 2 * n + 1, s, t);
for(int k = 1; k <= n; k++ ) {
if(k != s && k != t) {
cwl.add_edge(k, k + n, 1);
} else {
cwl.add_edge(k, k + n, cwl.INF);
}
}
for(int k = 0; k < vec.size(); k++ ) {
int x = vec[k].first, y = vec[k].second;
cwl.add_edge(x + n, y, cwl.INF);
cwl.add_edge(y + n, x, cwl.INF);
}
ans = min(ans, cwl.dinic());
}
}
if (ans >= cwl.INF) { ans = n; }
printf("%d
", ans);
}
return 0;
}