Bzoj 1391: [Ceoi2008]order 网络流,最大权闭合图

1391: [Ceoi2008]order

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1105  Solved: 331
[Submit][Status][Discuss]

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

Sample Output

50

HINT

Source

[Submit][Status][Discuss]

题解：

最大权闭合图。

又忘了咋连边了。。。QAQ

最大权闭合图：

构造一个原点S，汇点T。S -> 权值为正的点  连一条容量为权值的边。权值为负的点 -> T  连一条容量为权值的绝对值的边。原图中的边连INF。

但本题中有可以租的机器，每一次租也要花费代价。考虑最大权闭合图中的原图的边连INF的意义：使边的两个顶点必须同时选。但这道题可以不选但要付出代价，所以将原图中的边连容量为租的花费。

注意：一定要加 当前弧优化 。。。

 #include<bits/stdc++.h>
 using namespace std;
 #define MAXN 2520
 #define INF 1e9
 struct node
 {
     int begin,end,value,next;
 }edge[];
 int cnt,Head[MAXN],q[MAXN],dis[MAXN],cur[MAXN],S,T;
 void addedge(int bb,int ee,int vv)
 {
     edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].value=vv;edge[cnt].next=Head[bb];Head[bb]=cnt;
 }
 void addedge1(int bb,int ee,int vv)
 {
     addedge(bb,ee,vv);addedge(ee,bb,);
 }
 int read()
 {
     int s=,fh=;char ch=getchar();
     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
     return s*fh;
 }
 int BFS()
 {
     int head,tail,u,v,i;
     head=;tail=;q[tail]=S;
     memset(dis,-,sizeof(dis));dis[S]=;
     while(head!=tail)
     {
         head++;if(head==)head=;
         u=q[head];
         for(i=Head[u];i!=-;i=edge[i].next)
         {
             v=edge[i].end;
             if(edge[i].value>&&dis[v]<)
             {
                 dis[v]=dis[u]+;
                 tail++;if(tail==)tail=;
                 q[tail]=v;
             }
         }
     }
     if(dis[T]<=)return ;
     else return ;
 }
 int DFS(int u,int minflow)
 {
     int used=,ans,v,i;
     if(u==T)return minflow;
     for(i=cur[u];i!=-;i=edge[i].next)
     {
         v=edge[i].end;
         if(edge[i].value>&&dis[v]==dis[u]+)
         {
             ans=minflow-used;
             ans=DFS(v,min(ans,edge[i].value));
             edge[i].value-=ans;if(edge[i].value>)cur[u]=i;
             edge[i^].value+=ans;
             used+=ans;
             if(used==minflow)return minflow;
         }
     }
     if(used==)dis[u]=-;
     return used;
 }
 int Dinic()
 {
     int maxflow=,ans=,i;
     while(BFS()){for(i=;i<=T;i++)cur[i]=Head[i];ans=DFS(S,INF);if(ans==)break;maxflow+=ans;}
     return maxflow;
 }
 int main()
 {
     int ans=,n,m,s1,s2,s3,s4,s5,i,j;
     n=read();m=read();
     S=n+m+;T=S+;
     memset(Head,-,sizeof(Head));cnt=;
     for(i=;i<=n;i++)
     {
         s1=read();s2=read();
         addedge1(S,i,s1);ans+=s1;
         for(j=;j<=s2;j++)
         {
             s3=read();s4=read();
             addedge1(i,s3+n,s4);
         }
     }
     for(i=;i<=m;i++){s5=read();addedge1(n+i,T,s5);}
     printf("%d",ans-Dinic());
     return ;
 }