http://poj.org/problem?id=1966
题意:给出一个由n个点,m条边组成的无向图。求最少去掉多少点才能使得图中存在两点,它们之间不连通。
思路:将点i拆成a和b,连一条a->b的容量为1的边,代表这个点只能走一次,然后如果点i和点j有边相连,那么将bi和aj相连,bj和ai相连,容量为INF,代表这条边可以走INF次。
然后O(n^2)枚举源点和汇点跑最大流,算的最小的最大流就是答案。(这个时候的最大流代表的是S跑到T需要经过多少路径(最小割),如果得到的最大流是INF,那么代表图完全连通,因此还要和n取一个较小值)。
有一个以前模板的点要完善:初始化 index = S;
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define N 210
#define INF 0x3f3f3f3f
struct Edge {
int v, nxt, cap, init;
Edge () {}
Edge (int v, int nxt, int cap, int init) : v(v), nxt(nxt), cap(cap), init(init) {}
} edge[N*N];
int head[N], tot, dis[N], cur[N], pre[N], gap[N], n, m; void Add(int u, int v, int cap) {
edge[tot] = Edge(v, head[u], cap, cap); head[u] = tot++;
edge[tot] = Edge(u, head[v], , ); head[v] = tot++;
} int BFS(int S, int T) {
queue<int> que; que.push(T);
memset(dis, INF, sizeof(dis));
memset(gap, , sizeof(gap));
gap[]++; dis[T] = ;
while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(dis[v] == INF) {
dis[v] = dis[u] + ;
gap[dis[v]]++;
que.push(v);
}
}
}
} int ISAP(int S, int T, int n) {
BFS(S, T);
memcpy(cur, head, sizeof(cur));
int u = pre[S] = S, i, index, flow, ans = ;
while(dis[S] < n) {
if(u == T) {
flow = INF, index = S; // index = S !!!
for(i = S; i != T; i = edge[cur[i]].v)
if(flow > edge[cur[i]].cap) flow = edge[cur[i]].cap, index = i;
for(i = S; i != T; i = edge[cur[i]].v)
edge[cur[i]].cap -= flow, edge[cur[i]^].cap += flow;
ans += flow, u = index;
}
for(i = cur[u]; ~i; i = edge[i].nxt)
if(edge[i].cap > && dis[edge[i].v] == dis[u] - ) break;
if(~i) {
pre[edge[i].v] = u; cur[u] = i; u = edge[i].v;
} else {
if(--gap[dis[u]] == ) break;
int md = n;
for(i = head[u]; ~i; i = edge[i].nxt)
if(md > dis[edge[i].v] && edge[i].cap > ) md = dis[edge[i].v], cur[u] = i;
gap[dis[u] = md + ]++;
u = pre[u];
}
}
return ans;
} int main() {
while(~scanf("%d%d", &n, &m)) {
memset(head, -, sizeof(head)); tot = ;
for(int i = ; i <= n; i++) Add(i, i + n, );
for(int i = ; i <= m; i++) {
int u, v; scanf(" (%d, %d)", &u, &v);
u++, v++;
Add(u + n, v, INF); Add(v + n, u, INF);
}
int ans = INF;
for(int i = ; i < n; i++) {
for(int j = i + ; j <= n; j++) {
for(int k = ; k < tot; k++) edge[k].cap = edge[k].init;
int now = ISAP(i + n, j, * n);
if(now < ans) ans = now;
}
}
if(ans > n) ans = n;
printf("%d\n", ans);
}
return ;
}