现在的位置: 首页 > 算法 > 正文

poj2987 最大权闭合图

2018年02月23日 算法 ⁄ 共 1774字 ⁄ 字号 评论关闭

思路:对于每个雇员,值为正则连源点,值为负连接汇点,容量为绝对值,然后建立相关关系,容量为无穷大,跑一边最大流,然后所有正收益和减去最大流即为最大收益。

对于最少裁员几个,就是看与源点连接的残留网络中点的个数(不包括源点)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<cmath>
#define maxn 1<<29
#define mm 5555
using namespace std;
struct edge
{
    int from,to;
    long long cap,flow;
};
vector<int>g[mm];
vector<edge>edges;
int m,n,num;
bool vis[mm];
int d[mm];
int cur[mm];
void init()
{
    edges.clear();
    for(int i=0;i<=n+1;i++)g[i].clear();
}
void add(int u,int v,long long c)
{
    edges.push_back((edge){u,v,c,0});
    g[u].push_back(edges.size()-1);
    edges.push_back((edge){v,u,0,0});
    g[v].push_back(edges.size()-1);
}
bool bfs(int s,int t)
{
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(s);
    d[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        int size=g[u].size();
        for(int i=0;i<size;i++)
        {
            edge &e=edges[g[u][i]];
            if(!vis[e.to]&&e.cap>e.flow)
            {
                vis[e.to]=1;
                d[e.to]=d[u]+1;
                q.push(e.to);
            }
        }
    }
    return vis[t];
}
long long dfs(int u,int t,long long mi)
{
    if(u==t||mi==0)return mi;
    long long flow=0,f;
    int size=g[u].size();
    for(int &i=cur[u];i<size;i++)
    {
        edge &e=edges[g[u][i]];
        if(d[u]+1==d[e.to]&&(f=dfs(e.to,t,min(mi,e.cap-e.flow)))>0)
        {
            e.flow+=f;
            edges[g[u][i]^1].flow-=f;
            flow+=f;
            mi-=f;
            if(mi==0)break;
        }
    }
    return flow;
}
long long dinic(int s,int t)
{
    long long flow=0;
    while(bfs(s,t))
    {
        memset(cur,0,sizeof(cur));
        flow+=dfs(s,t,maxn);
    }
    return flow;
}
void dd(int u)
{
    vis[u]=1;
    num++;
    int size=g[u].size();
    for(int i=0;i<size;i++)
    {
        edge &e=edges[g[u][i]];
        if(e.flow<e.cap&&!vis[e.to])
        {
            dd(e.to);
        }
    }
}
int main()
{
    long long ss;
    int u,v;
    long long c;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        ss=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&c);
            if(c>0)
            {
                add(0,i,c);
                ss+=c;
            }
            else add(i,n+1,-c);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v,maxn);
        }
        num=0;
        long long ans=ss-dinic(0,n+1);
        memset(vis,0,sizeof(vis));
        dd(0);
        printf("%d %lld\n",num-1,ans);
    }
    return 0;
}
【上篇】
【下篇】

抱歉!评论已关闭.