加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

POJ PKU 1815 最小割,寻找最优割点

(2010-10-02 20:32:23)
标签:

poj

pku

1815

最小割

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
            {
                while(tail > 0 && u != s && cur[u] == -1) u = e[que[--tail]].from;
                cur[u] = e[cur[u]].next;
            }
    }
    return maxflow;
}
int n, s, t, num, jeo[size], ans[size], x[size][size];
bool vst[size];
int main()
{
    while(scanf("%d%d%d", &n, &s, &t) != EOF)
    {
        memset(v, -1, sizeof(int) * (n + n + 1)); cnt = 0;
        for(int i = 1; i <= n; i++)
            if (i != s && i != t) insert(i, i + n, 1);
            else insert(i, i + n, Max);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                scanf("%d", &x[i][j]);
                if (i == j || j == s || i == t) continue;
                if (x[i][j]) insert(i + n, j, Max);
            }
        int jeogia = Dinic(n + n + 1, s, t + n); num = 0;
        if (jeogia == Max) {printf("NO ANSWER!\n"); continue;}
        memset(vst, 0, sizeof(bool) * (n + 1));
        for(int i = 1; i <= n; i++)
        {
            if (i == t || i == s) continue;
            vst[i] = 1;
            memset(v, -1, sizeof(int) * (n + n + 1)); cnt = 0;
            for(int j = 1; j <= n; j++)
                if (vst[j]) continue;
                else if (j != s && j != t) insert(j, j + n, 1);
                else insert(j, j + n, Max);
            for(int j = 1; j <= n; j++)
                for(int k = 1; k <= n; k++)
                {
                    if (k == j || k == s || j == t || vst[j] || vst[k]) continue;
                    if (x[j][k]) insert(j + n, k, Max);
                }
            int tmp = Dinic(n + n + 1, s, t + n);
            if (tmp < jeogia)
            {
                jeo[num++] = i;
                jeogia = tmp;
            }
            else vst[i] = 0;
        }
        printf("%d\n", num);
        for(int i = 0; i < num; i++)
        {
            printf("%d", jeo[i]);
            if (i == num - 1) printf("\n");
            else printf(" ");
        }
    }
    return 0;
}
 

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有