网络流/最小割
暴力建图就好了……S->i 容量为收益，i->j+n 容量为租金，j+n->T容量为购买所花的钱。
如果亏钱的话那么割掉的就是收益，表示不赚钱。
如果租金大于购买所花的钱就会割掉购买的钱（因为流量限制住了……）
表示T到死啊……copy了Hzwer……orz
#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 0x7fffffff
using namespace std;
int T,n,m,cnt=,ans,cur[],q[],head[],h[];
struct data{int to,next,v;}e[];
void ins(int u,int v,int w)
{cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v,int w)
{ins(u,v,w);ins(v,u,);}
bool bfs()
{
int t=,w=,i,now;
for(int i=;i<=T;i++)h[i]=-;
q[]=h[]=;
while(t!=w)
{
now=q[t];t++;if(t==)t=;
for(i=head[now];i;i=e[i].next)
{
if(e[i].v&&h[e[i].to]<)
{h[e[i].to]=h[now]+;q[w++]=e[i].to;if(w==)w=;}
}
}
if(h[T]==-)return ;return ;
}
int dfs(int x,int f)
{
if(x==T)return f;
int w,used=;
for(int i=cur[x];i;i=e[i].next)
{
if(e[i].v&&h[e[i].to]==h[x]+)
{
w=f-used;
w=dfs(e[i].to,min(w,e[i].v));
e[i].v-=w;if(e[i].v>)cur[x]=i;e[i^].v+=w;
used+=w;if(used==f)return f;
}
}
if(!used)h[x]=-;
return used;
}
void dinic(){while(bfs()){for(int i=;i<=T;i++)cur[i]=head[i];ans-=dfs(,inf);}}
int main()
{
scanf("%d%d",&n,&m);
T=n+m+;
int a,b,c,d;
for(int i=;i<=n;i++)
{
scanf("%d%d",&a,&b);
insert(,i,a);ans+=a;
for(int j=;j<=b;j++)
{
scanf("%d%d",&c,&d);
insert(i,n+c,d);
}
}
for(int i=;i<=m;i++)
{
scanf("%d",&a);
insert(n+i,T,a);
}
dinic();
printf("%d",ans);
return ;
}
（Hzwer）
//BZOJ 2768
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,M=,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
int n,m,ans;
struct edge{
int to,v;
};
edge E[M];
int head[N],next[M],cnt;
void add(int x,int y,int v){
E[++cnt]=(edge){y,v};
next[cnt]=head[x]; head[x]=cnt;
E[++cnt]=(edge){x,};
next[cnt]=head[y]; head[y]=cnt;
}
int s,t,cur[N],d[N],Q[N];
void init(){
n=getint();m=getint();
cnt=;ans=;
s=; t=n+m+;
int x,y,a,b;
F(i,,n){
x=getint(); y=getint();
ans+=x;
add(s,i,x);
F(j,,y){
a=getint(); b=getint();
add(i,n+a,b);
}
}
F(i,,m){
x=getint();
add(n+i,t,x);
}
}
bool mklevel(){
F(i,s,t) d[i]=-;
d[s]=;
int l=,r=-;
Q[++r]=s;
while(l<=r){
int x=Q[l++];
for(int i=head[x];i;i=next[i])
if (d[E[i].to]==- && E[i].v){
d[E[i].to]=d[x]+;
Q[++r]=E[i].to;
}
}
return d[t]!=-;
}
int dfs(int x,int a){
if (x==t||a==) return a;
int flow=;
for(int &i=cur[x];i && flow<a;i=next[i])
if (d[E[i].to]==d[x]+ && E[i].v){
int f=dfs(E[i].to,min(a-flow,E[i].v));
E[i].v-=f;
E[i^].v+=f;
flow+=f;
}
if (!flow) d[x]=-;
return flow;
}
void Dinic(){
while(mklevel()){
F(i,s,t) cur[i]=head[i];
ans-=dfs(s,INF);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("2768.in","r",stdin);
freopen("2768.out","w",stdout);
#endif
init();Dinic();
printf("%d\n",ans);
return ;
}
(My)
1391: [Ceoi2008]order
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 746 Solved: 230
[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
