Description
有N个工作，M种机器，每种机器你可以租或者买过来. 每个工作包括若干道工序，每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。 现在给出这些参数，求最大利润
Input
第一行给出 N,M(1<=N<=1200,1<=M<=1200) 下面将有N块数据，每块数据第一行给出完成这个任务能赚到的钱(其在[1,5000])及有多少道工序 接下来若干行每行两个数，分别描述完成工序所需要的机器编号及租用它的费用(其在[1,20000]) 最后M行，每行给出购买机器的费用(其在[1,20000])
Output
最大利润
Sample Input
2 3
100 2
1 30
2 20
100 2
1 40
3 80
50
80
110
100 2
1 30
2 20
100 2
1 40
3 80
50
80
110
Sample Output
50
HINT
Solution
最小割，因为可以租用，所以就在工作和机器之间的边上代价赋为租用费用即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N=5000,M=4000000; int n,m; namespace DINIC { int S,T,tot,Next[M],head[N],tree[M],val[M],Queue[N],h[N],cur[N]; void add(int x,int y,int z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } void add_edge(int x,int y,int z) { add(x,y,z); add(y,x,0); } bool bfs() { int t=0,w=1; memset(h,-1,sizeof(h)); Queue[1]=S;h[S]=0; while (t!=w) { int u=Queue[++t]; for (int i=head[u];i;i=Next[i]) if (val[i]!=0) { int v=tree[i]; if (h[v]==-1) { Queue[++w]=v; h[v]=h[u]+1; } } } return h[T]!=-1; } int dfs(int u,int low) { if (u==T) return low; int used=0; for (int i=cur[u];i;i=Next[i]) { cur[u]=i; int v=tree[i]; if (val[i]>0&&h[v]==h[u]+1) { int w=dfs(v,min(val[i],low-used)); val[i]-=w;val[i^1]+=w; used+=w; if (used==low) return low; } } if (used==0) h[u]=-1; return used; } int dinic() { int ans=0; while (bfs()) { for (int i=1;i<=T;i++) cur[i]=head[i]; ans+=dfs(S,1<<29); } return ans; } } int main() { using namespace DINIC; scanf("%d%d",&n,&m); S=n+m+1;T=n+m+2; tot=1; int sum=0; for (int i=1;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); add_edge(S,i,x); sum+=x; for (int j=1;j<=y;j++) { int a,b; scanf("%d%d",&a,&b); add_edge(i,a+n,b); } } for (int i=1;i<=m;i++) { int x; scanf("%d",&x); add_edge(i+n,T,x); } printf("%d\n",sum-dinic()); return 0; } |
