思路:对于每个雇员,值为正则连源点,值为负连接汇点,容量为绝对值,然后建立相关关系,容量为无穷大,跑一边最大流,然后所有正收益和减去最大流即为最大收益。
对于最少裁员几个,就是看与源点连接的残留网络中点的个数(不包括源点)。
#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; }