[POJ3762 The Bonus Salary!]费用流

【题目大意】
给N个时间段，每个时间段只能用一次，然后有k天供你用这些时间段。
同一天里，时间段不能有重叠。
问最多能用到多少费用？
【算法分析】
先对所有时刻进行离散化。
然后每个时刻向下一个时刻连容量为k，费用为0的边。
接着对于每个区间 [L,R]，对对应的时间连边L->R费用为区间费用，容量为1.
然后源点要退一个格子。
最后搞一个最大费用最大流就可以了。
【其它】
1CE，悲剧，POJ的iostream里不含sort函数。。。
【CODE】
#include #include #include #include #include using namespace std;
const int N=20000;
struct edge{int x,y,c,w;edge *op,*next;}g[N],*ls[N],*fa[N];
struct Node{int x,y,w;}p[N];
int n,k,tot,e,cost;
int lx[N],d[N],v[N],List[N];

void init(){
tot=0; e=0; memset(ls,0,sizeof(ls));
for (int i=1;i<=n;i++){
int h1,m1,s1,h2,m2,s2;
scanf("%d:%d:%d %d:%d:%d %d",&h1,&m1,&s1,&h2,&m2,&s2,&p[i].w);
p[i].x=h1*3600+m1*60+s1;
p[i].y=h2*3600+m2*60+s2;
lx[++tot]=p[i].x;
lx[++tot]=p[i].y;
}
}

void addedge(int x,int y,int c,int w){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].w=w; g[e].next=ls[x];
ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w; g[e].next=ls[y];
ls[y]=&g[e]; g[e].op=&g[e-1];
}

int Find(int x){
int l=1,r=tot,mid;
while (l mid=(l+r)/2;
if (x>lx[mid]) l=mid+1;
else r=mid;
}
return l;
}

void Lisan(){
sort(lx+1,lx+tot+1);
int tmp=tot,i; tot=0;
for (i=1;i<=tmp;i++)
if (!tot || lx[tot]!=lx[i]) lx[++tot]=lx[i];
for (i=1;i<=n;i++)
addedge(Find(p[i].x),Find(p[i].y),1,p[i].w);
for (i=1;i addedge(i,i+1,k,0);
addedge(0,1,k,0);
}

bool spfa(){
memset(d,200,sizeof(d));
memset(v,0,sizeof(v));
int head=0,tail=1;
List[1]=0; v[0]=1; d[0]=0;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=ls[List[head]];t;t=t->next)
if (t->c && d[t->x]+t->w>d[t->y]){
d[t->y]=d[t->x]+t->w;
fa[t->y]=t;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
List[tail]=t->y;
}
}
v[List[head]]=0;
}
if (d[tot]<=0) return false;
return true;
}

void change(){
int nf=0x7FFFFFFF;
for (int i=tot;i;i=fa[i]->x)
if (fa[i]->c cost+=nf*d[tot];
for (int i=tot;i;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
}

void MCMF(){
cost=0;
while (spfa()) change();
}

int main(){
while (scanf("%d%d",&n,&k)!=EOF){
init();
Lisan();
MCMF();
printf("%dn",cost);
}
return 0;
}