首页 > 代码库 > Poj 1815 Friendship 枚举+求最小割

Poj 1815 Friendship 枚举+求最小割

2024-07-14 11:22:48   223人阅读

给以一个图和两个点S，T，问你拿掉最少多少个点可以使得S和T不连通。输出点数并且输出拿掉的是哪些点，如果有多种方法就输出字典序最小的那个。

这就是一个求最小点割集的问题。无向(有向)图G中，给定源点s和终点t，至少要删去多少个点(具体一点，删哪些点)，使得s和t不连通。这个问题就是点连通度，也叫最小点割集。

解法其实理解起来不难，只要把图中的每一个点v拆成v‘,v‘‘两个点，并建立<v‘,v‘‘>权为1，这样就把最小点割集转化成求最小割的问题。

对于原图的转化也很简单，对于原来的每条边，转化成这样的形式u‘->u‘‘->v‘->v‘‘,即连一条<u‘‘,v‘>的边，对于无向图只要反过来再连一次就好，这些边的容量当然为正无穷。然后只要求一次最小割，出来的结果自然就是要去掉多少个点了。

对于这道题，建立源点s并且连边<s,S‘>容量为正无穷，并且建立汇点t连边<T‘‘,t>容量为正无穷，最后求一次最小割即可。

对于一开始判定是不是无解的问题，显然只有S和T直接相连的时候才会无解，这个时候对应的边应该是<S‘‘,T‘>

对于最后要输出字典序最小的方案，我只会用枚举的方法，从小到大依次删去每一个除了S和T之外的点，其实拆点了之后操作很简单，只要删去<v‘,v‘‘>就好了，删去这个点之后求一下最小割，如果最小割变小了，则在解的集合里面加入这个点，直到流量最后变为0了。如果割没有变小别忘记把删去的边加回去。

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>using namespace std;typedef long long LL;const int maxn = 405;const int INF = INT_MAX / 2;int N,S,T,cap[maxn][maxn],flow[maxn][maxn],s,t;int mp[maxn][maxn];void build_graph() {    memset(cap,0,sizeof(cap));    s = 0; t = 2 * N + 1;    cap[s][S] = INF;    cap[T + N][t] = INF;    for(int i = 1;i <= N;i++) {        cap[i][i + N] = 1;        for(int j = 1;j <= N;j++) if(mp[i][j] && i != j) {            cap[i + N][j] = INF;        }    }     cap[S][S + N] = cap[T][T + N] = INF;}int level[maxn],q[maxn],qs,qe;bool bfs() {    memset(level,0,sizeof(level));    qs = qe = 0;    q[qe++] = s;    level[s] = 1;    while(qs < qe) { int now = q[qs++]; if(now == t) break;        for(int i = s;i <= t;i++) {            if(cap[now][i] - flow[now][i] && !level[i]) {                q[qe++] = i; level[i] = level[now] + 1;            }        }    }    return level[t];}int dfs(int now,int alpha) {    if(now == t) return alpha;    int sum = 0;    for(int i = s;i <= t && alpha;i++) {        if(cap[now][i] - flow[now][i] && level[now] + 1 == level[i]) {            int ret = dfs(i,min(alpha,cap[now][i] - flow[now][i]));            flow[now][i] += ret; flow[i][now] -= ret;            sum += ret; alpha -= ret;        }    }    //printf("now is %d,sum is %d\n",now,sum);    if(sum == 0) level[now] = -1;    return sum;}void solve() {    if(cap[S + N][T]) {        puts("NO ANSWER!");        return;    }    int ansval = 0,cnt = 0;    while(bfs()) ansval += dfs(S,INF);    printf("%d\n",ansval);    //开始枚举    for(int i = 1;i <= N;i++) if(i != S && i != T) {        memset(flow,0,sizeof(flow));        cap[i][i + N] = 0;        int nowans = 0;        while(bfs()) nowans += dfs(S,INF);        if(nowans != ansval) {            if(cnt != 0) putchar(‘ ‘);            printf("%d",i);            ansval = nowans;            cnt++;        } else cap[i][i + N] = 1;        if(ansval == 0) break;    }    if(cnt) puts("");}int main() {    while(~scanf("%d%d%d",&N,&S,&T)) {        for(int i = 1;i <= N;i++) {            for(int j = 1;j <= N;j++) {                scanf("%d",&mp[i][j]);            }        }        build_graph();        solve();    }    return 0;}

　　


联系
我们