poj1815(最小割点集)

【题目大意】
现代社会人们都靠电话通信。A 与 B 能通信当且仅当 A 知道 B 的电话号或者 A
知道 C 的电话号且 C 与 B 能通信。若 A 知道 B 的电话号，那么 B 也知道 A 的电
话号。然而不好的事情总是会发生在某些人身上，比如他的电话本丢了，同时他
又换了电话号，导致他跟所有人失去了联系。现在给定 N 个人之间的通信关系
以及特定的两个人 S 和 T，问最少几个人发生不好的事情可以导致 S 与 T 无法通
信并输出这些人。如果存在多组解，输出字典序最小的一组。（2 <= N <= 200）
【建模方法】
此题是求一个最小点割集，但是要求输出方案且要字典序最小。首先仍是拆点构
图，求一次最小割记为 ans。之后我们采取贪心的策略，从 1 至 N 枚举删点，如
果最小割不变，说明该点不可能在最小割中，我们再把该点加入到网络中；否则
最小割一定变小了，用这个较小值更新 ans，记录该点是一个解并不再将其放回。

重复这个过程，把所有点都扫描一遍后结果就

#include
#include
#include
#include
using namespace std;
int bmap[205][205];
typedef int cap_type;
#define MAX_V 800 + 30 + 16
struct edge
{int to, rev;cap_type cap;edge(int to, cap_type cap, int rev) : to(to), cap(cap), rev(rev){}
};vector  G[MAX_V];
int level[MAX_V];
int iter[MAX_V];
void add_edge(int from, int to, int cap)
{G[from].push_back(edge(to, cap, G[to].size()));G[to].push_back(edge(from, 0, G[from].size() - 1));
}
void bfs(int s)
{memset(level, -1, sizeof(level));queue que;level[s] = 0;que.push(s);while (!que.empty()){int v = que.front();que.pop();for (int i = 0; i < G[v].size(); ++i){edge &e = G[v][i];if (e.cap > 0 && level[e.to] < 0){level[e.to] = level[v] + 1;que.push(e.to);}}}
}
cap_type dfs(int v, int t, cap_type f)
{if (v == t){return f;}for (int &i = iter[v]; i < G[v].size(); ++i){edge &e = G[v][i];if (e.cap > 0 && level[v] < level[e.to]){cap_type d = dfs(e.to, t, min(f, e.cap));if (d > 0){e.cap -= d;G[e.to][e.rev].cap += d;return d;}}}return 0;
}
cap_type max_flow(int s, int t)
{cap_type flow = 0;for (;;){bfs(s);if (level[t] < 0){return flow;}memset(iter, 0, sizeof(iter));cap_type f;while ((f = dfs(s, t, 0x3f3f3f3f)) > 0){flow += f;}}
}
int ans[205];
int vis[205];
int tot = 0;
int main()
{int n,s,t;while(scanf("%d%d%d",&n,&s,&t)!=EOF){for(int j=0;j<2*n+10;j++) G[j].clear(); tot = 0;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&bmap[i][j]);if(bmap[s][t]==1) {printf("NO ANSWER!\n"); return 0; }for(int i=1;i<=n;i++){if(i==s||i==t) add_edge(i,i+n,0x3f3f3f3f);else add_edge(i,i+n,1);}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){if(bmap[i][j]==0) continue;add_edge(i+n,j,0x3f3f3f3f);add_edge(j+n,i,0x3f3f3f3f);}int res = max_flow(s,t+n);memset(vis,0,sizeof(vis));printf("%d\n",res);for(int i=1;i<=n;i++){if(i==s||i==t) continue;vis[i] = 1;for(int j=0;j<2*n+10;j++) G[j].clear();for(int j=1;j<=n;j++){if(vis[j]) continue;if(j==s||j==t) add_edge(j,j+n,0x3f3f3f3f);else add_edge(j,j+n,1);}for(int j=1;j<=n;j++){if(vis[j]) continue;for(int k=1;k<=n;k++){if(vis[k]||!bmap[j][k]||j==k) continue;add_edge(j+n,k,0x3f3f3f3f);}}int tmp = max_flow(s,t+n);//printf("%d %d %d\n",i,tmp,res);if(tmp0){for(int i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！