POJ PKU 1815 最小割,寻找最优割点
(2010-10-02 20:32:23)
标签:
pojpku1815最小割it |
分类: 网络流 |
题目描述:给你N个节点,和节点之间的关联关系。然后给你其中两个不同的节点S,T。问你最少去掉多少个节点可以使S,T之间没有关联。输出这些点,如果有多个解,输出一个字典序最小的。
解题报告:
拆点,点i分为i和i’,连接i到i’,容量为1。(如果是S和T点,容量为无穷)
如果点a到点b有边,连接a’ 到b,这样求最小割就是最少的节点数。
然后就是怎样寻找答案所需的最优的割点了。
枚举割点:
按字典序枚举到点i,就重新构图(不要点i和之前已经删除的点),如果这样的图求的的最大流小于原来的值,就说明这是一个有效割点,保存之。
这样就是答案。
代码如下:
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define Max 0x1fffffff
#define size 500
struct edge{int from, to, val, next;}e[140000];
int v[size], que[size], dis[size], cnt, cur[size];
void insert(int from, int to, int va)
{
e[cnt].from = from, e[cnt].to = to; e[cnt].val = va;
e[cnt].next = v[from];v[from] = cnt++;
e[cnt].from = to, e[cnt].to = from; e[cnt].val = 0;
e[cnt].next = v[to];v[to] = cnt++;
}
bool bfs(int n, int s, int t)
{
int head, tail, id;
head = tail = 0; que[tail++] = s;
memset(dis, -1, sizeof(int) * n);dis[s] = 0;
while(head < tail) // bfs,得到顶点i的距s的最短距离dis[i]
for(id = v[que[head++]]; id != -1; id = e[id].next)
if (e[id].val > 0 && dis[e[id].to] == -1)
{
dis[e[id].to] = dis[e[id].from] + 1;
que[tail++] = e[id].to;
if (e[id].to == t) return true;
}
return false;
}
int Dinic(int n, int s, int t)
{
int maxflow = 0, tmp, i;
while(bfs(n, s, t))
{
int u = s, tail = 0;
for(i = 0; i < n; i++) cur[i] = v[i];
while(cur[s] != -1)
if (u != t && cur[u] != -1 && e[cur[u]].val > 0 && dis[u] != -1 && dis[u] + 1 == dis[e[cur[u]].to])
{que[tail++] = cur[u]; u = e[cur[u]].to;}
else if (u == t)
{
for(tmp = Max, i = tail - 1; i >= 0; i--) tmp = min(tmp, e[que[i]].val);
for(maxflow += tmp, i = tail - 1; i >= 0; i--)
{
e[que[i]].val -= tmp;
e[que[i] ^ 1].val += tmp;
if (e[que[i]].val == 0) tail = i;
}
u = e[que[tail]].from;
}
else
{