poj2987最大权闭包（输出最少建塔个数）

题意：

公司要裁员，每个员工被裁掉之后都会有一定的收益（正或者负），有一些员工之间有限制关系，就是裁掉谁之前必须要先裁掉另一个人，问公司的最大收益和最大收益前提下的最小裁员人数？

思路：

收益有正、有负，员工之间有限制关系，那么是不是瞬间就想到了杭电的那个通讯塔的那么题目，虽然那个是最大点权独立集，而这二个是最大权闭包，但是我感觉两者想法一样，只不过中间是通过一些转换了，这个题有个特别的地方，就是输出最小裁员人数，这个还真不知道怎么弄，然后在网上看了下，说是在残余网络上直接从起点开始搜索，能走到几个就是几，写到是很好写，关键是理解为什么？这个据说论文上有，我说下我的理解，我感觉可能是这样，ss-a-b-tt,如果跑完之后ss-a还有流量会怎样？是不是还有流量就证明挣的钱比花的钱多，那么我们就删除点a,b就行了，把问题复杂化也一样，ss-a-b-tt
ss-a-c-tt ,就是说删除a之前要删除b,c才行，如果ss-a还有流量就证明ss-a > (b->tt)+(c->tt)那么删除他们三个是最优的......

#include<queue>

#include<stdio.h>

#include<string.h>

#define N_node 5500

#define N_edge 150000

#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef struct

{

    int to ,next;

    long long cost;

}STAR;

typedef struct

{

    int x ,t;

}DEP;

DEP xin ,tou;

STAR E[N_edge];

int list[N_node] ,listt[N_node] ,tot;

int deep[N_node];

void add(int a ,int b ,long long c)

{

    E[++tot].to = b;

    E[tot].cost = c;

    E[tot].next = list[a];

    list[a] = tot;

    E[++tot].to = a;

    E[tot].cost = 0;

    E[tot].next = list[b];

    list[b] = tot;

}

long long minn(long long x ,long long y)

{

    return x < y ? x : y;

}

bool BFS_Deep(int s ,int t ,int n)

{

    memset(deep ,255 ,sizeof(deep));

    xin.x = s ,xin.t = 0;

    deep[xin.x] = xin.t;

    queue<DEP>q;

    q.push(xin);

    while(!q.empty())

    {

        tou = q.front();

        q.pop();

        for(int k = list[tou.x] ;k ;k = E[k].next)

        {

            xin.x = E[k].to;

            xin.t = tou.t + 1;

            if(deep[xin.x] != -1 || !E[k].cost)

            continue;

            deep[xin.x] = xin.t;

            q.push(xin);

        }

    }

    for(int i = 0 ;i <= n ;i ++)

    listt[i] = list[i];

    return deep[t] != -1;

}

long long DFS_Flow(int s ,int t ,long long flow)

{

    if(s == t) return flow;

    long long nowflow = 0;

    for(int k = listt[s] ;k ;k = E[k].next)

    {

        listt[s] = k;

        int to = E[k].to;

        long long c = E[k].cost;

        if(deep[to] != deep[s] + 1 || !c)

        continue;

        long long tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));

        nowflow += tmp;

        E[k].cost -= tmp;

        E[k^1].cost += tmp;

        if(nowflow == flow) break;

    }

    if(!nowflow) deep[s] = 0;

    return nowflow;

}

long long DINIC(int s ,int t ,int n)

{

    long long Ans = 0;

    while(BFS_Deep(s ,t ,n))

    {

        Ans += DFS_Flow(s ,t ,INF);

    }

    return Ans;

}

int SS;

int mark[N_node];

void DFS(int s)

{

    mark[s] = 1;

    for(int k = list[s] ;k ;k = E[k].next)

    {

        if(!mark[E[k].to] && E[k].cost)

        {

            SS ++;

            DFS(E[k].to);

        }

    }

    return ;

}

int main ()

{

    int n ,m ,i ,a ,b;

    long long c ,S;

    while(~scanf("%d %d" ,&n ,&m))

    {

        int ss = 0 ,tt = n + 1;

        memset(list ,0 ,sizeof(list));

        tot = 1;

        for(S = 0 ,i = 1 ;i <= n ;i ++)

        {

            scanf("%lld" ,&c);

            c > 0 ? add(ss ,i ,c) : add(i ,tt ,-c);

            if(c > 0) S += c;

        }

        for(i = 1 ;i <= m ;i ++)

        {

            scanf("%d %d" ,&a ,&b);

            add(a ,b ,INF);

        }

        S -= DINIC(ss ,tt ,tt);

        memset(mark ,0 ,sizeof(mark));

        SS = 0;

        DFS(ss);

        printf("%d %lld\n" ,SS ,S);

    }

    return 0;

}

巴特西

poj2987最大权闭包（输出最少建塔个数）

最新文章

热门文章